题目描述

$T$ 個のテストケースについて、次の問題を解いてください。

整数 $N$ と文字列 $S$ が与えられるので、以下の条件を全て満たす文字列 $X$ の数を $998244353$ で割った余りを求めてください。

• $X$ は英大文字のみからなる長さ $N$ の文字列
• $X$ は回文
• 辞書順で $X\ \le\ S$
  • すなわち、 $X=S$ であるか、辞書順で $X$ が $S$ より前に来る

输入格式

入力は以下の形式で標準入力から与えられる。

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

ただし、 $\mathrm{case}_i$ は $i$ 個目のテストケースを表す。

各テストケースは以下の形式で与えられる。

$N$ $S$

输出格式

全体で $T$ 行出力せよ。
$i$ 行目には $i$ 個目のテストケースに対する答えを整数として出力せよ。

题目大意

给定正整数 $N$ 和长度为 $N$ 的字符串 $S$，你的任务是计算有多少个长度为 $N$ 的回文字符串 $X$，使得 $X \leq S$。计算结果对 $998244353$ 取模。$S$ 和 $T$ 均只包含大写英文字母。

总共有 $T$ 组数据。$T \leq 250000$, $N \leq 10^6$，所有 $S$ 的字母总数不超过 $10^6$。

5
3
AXA
6
ABCZAZ
30
QWERTYUIOPASDFGHJKLZXCVBNMQWER
28
JVIISNEOXHSNEAAENSHXOENSIIVJ
31
KVOHEEMSOZZASHENDIGOJRTJVMVSDWW

24
29
212370247
36523399
231364016

提示

制約

• $1\ \le\ T\ \le\ 250000$
• $N$ は $1$ 以上 $10^6$ 以下の整数
• ひとつの入力について、含まれるテストケースの $N$ の総和は $10^6$ を超えない
• $S$ は英大文字のみからなる長さ $N$ の文字列

Sample Explanation 1

この入力には $5$ 個のテストケースが含まれます。 $1$ 個目のテストケース: 問題文中の条件を満たす文字列は AAA$,$ ABA$,$ ACA$,...,$ AXA の $24$ 個です。 $2$ 個目のテストケース: $S$ が回文であるとは限りません。 $3$ 個目のテストケース: $998244353$ で割った余りを求めることに注意してください。