(∀x∀)

题目描述

对于 $T$ 个测试用例,解决下面的问题。

给定整数 $N$ 和字符串 $S$,求满足以下所有条件的字符串 $X$ 的个数,对 $998244353$ 取模。

• $X$ 是由大写英文字母组成的长度为 $N$ 的字符串。
• $X$ 是回文串。
• $X \le S$,即 $X=S$,或 $X$ 的字典序小于 $S$。

输入格式

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

T
case_1
case_2
⋮
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$ 取模后的答案。

数据范围

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