当前没有测试数据。

E - (∀x∀)

得分：$500$ 分

问题描述

请解决以下问题，对于 $T$ 个测试用例。

给定一个整数 $N$ 和一个字符串 $S$，找出满足以下所有条件的字符串 $X$ 的数量，取模 $998244353$。

• $X$ 是由大写英文字母组成的长度为 $N$ 的回文字符串。
• $X$ 在字典序中小于等于 $S$：
  • 即 $X=S$ 或 $X$ 在字典序上小于 $S$。

约束条件

• $1 \le T \le 250000$
• $N$ 是一个介于 $1$ 到 $10^6$（含）之间的整数。
• 在单个输入中，所有测试用例中 $N$ 的总和不超过 $10^6$。
• $S$ 是由大写英文字母组成的长度为 $N$ 的字符串。

---

输入

从标准输入中按以下格式给出：

$T$

$\mathrm{case}_1$

$\mathrm{case}_2$

$\vdots$

$\mathrm{case}_T$

这里，$\mathrm{case}_i$ 表示第 $i$ 个测试用例。

每个测试用例的格式如下：

``` $N$ $S$ ```

输出

输出 $T$ 行。 第 $i$ 行应该包含第 $i$ 个测试用例的答案，作为一个整数。

---

5
3
AXA
6
ABCZAZ
30
QWERTYUIOPASDFGHJKLZXCVBNMQWER
28
JVIISNEOXHSNEAAENSHXOENSIIVJ
31
KVOHEEMSOZZASHENDIGOJRTJVMVSDWW

24
29
212370247
36523399
231364016

这个输入包含五个测试用例。

测试用例 #1：
满足条件的 $24$ 个字符串是 AAA$,$ ABA$,$ ACA$,...,$ AXA。

测试用例 #2：
$S$ 可能不是回文字符串。

测试用例 #3：
请确保计数取模 $998244353$。