AT_abc242_e [ABC242E] (∀x∀)

[problemUrl]: https://atcoder.jp/contests/abc242/tasks/abc242_e $ 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 $ 個目のテストケースに対する答えを整数として出力せよ。

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