题目描述

对于给定的 $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$ $case_1$ $case_2$ $\vdots$ $case_T$

这里，$case_i$ 表示第 $i$ 个测试用例。

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

$N$ $S$

输出

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

示例输入1

5
3
AXA
6
ABCZAZ
30
QWERTYUIOPASDFGHJKLZXCVBNMQWER
28
JVIISNEOXHSNEAAENSHXOENSIIVJ
31
KVOHEEMSOZZASHENDIGOJRTJVMVSDWW

示例输出1

24
29
212370247
36523399
231364016

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

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

测试用例＃2：
$S$ 可能不是一个回文串。

测试用例＃3：
确保取模 $998244353$。