E - (∀x∀) 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

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

入力例 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 で割った余りを求めることに注意してください。

Score : 500 points

Problem Statement

Solve the following problem for T test cases.

Given an integer N and a string S, find the number of strings X that satisfy all of the conditions below, modulo 998244353.

  • X is a string of length N consisting of uppercase English letters.
  • X is a palindrome.
  • X \le S in lexicographical order.
    • That is, X=S or X is lexicographically smaller than S.

Constraints

  • 1 \le T \le 250000
  • N is an integer between 1 and 10^6 (inclusive).
  • In a single input, the sum of N over the test cases is at most 10^6.
  • S is a string of length N consisting of uppercase English letters.

Input

Input is given from Standard Input in the following format:

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

Here, \mathrm{case}_i represents the i-th test case.

Each test case is in the following format:

N
S

Output

Print T lines. The i-th line should contain the answer for the i-th test case as an integer.

Sample Input 1

5
3
AXA
6
ABCZAZ
30
QWERTYUIOPASDFGHJKLZXCVBNMQWER
28
JVIISNEOXHSNEAAENSHXOENSIIVJ
31
KVOHEEMSOZZASHENDIGOJRTJVMVSDWW

Sample Output 1

24
29
212370247
36523399
231364016

This input contains five test cases.

Test case #1:
The 24 strings satisfying the conditions are AAA, ABA, ACA,..., AXA.

Test case #2:
S may not be a palindrome.

Test case #3:
Be sure to find the count modulo 998244353.