問題文

$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$ 個目のテストケースに対する答えを整数として出力せよ。

入力例 1

5
3
AXA
6
ABCZAZ
30
QWERTYUIOPASDFGHJKLZXCVBNMQWER
28
JVIISNEOXHSNEAAENSHXOENSIIVJ
31
KVOHEEMSOZZASHENDIGOJRTJVMVSDWW

出力例 1

24
29
212370247
36523399
231364016

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

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

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

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