配点 : $500$ 点

問題文

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

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

• $X$ は英大文字のみからなる長さ $N$ の文字列
• $X$ は回文
• 辞書順で $X \le 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

この入力には $5$ 個のテストケースが含まれます。

$1$ 個目のテストケース: 問題文中の条件を満たす文字列は AAA$,$ ABA$,$ ACA$,...,$ AXA の $24$ 個です。

$2$ 個目のテストケース: $S$ が回文であるとは限りません。

$3$ 個目のテストケース: $998244353$ で割った余りを求めることに注意してください。