A - Welcome to NPCAPC Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

英大文字と英小文字からなる長さ N の文字列のうち、 NPCAPC と npcapc の両方を部分文字列(連続でなくてもよい)として含むものの個数を 998244353 で割ったあまりを求めてください。

T 個のテストケースが与えられるので、それぞれについて解いてください。

制約

  • 1 \leq N\leq 10^9
  • 1 \leq T\leq 5000

部分点

この問題には複数の部分点が設定されている。

  • N \leq 2\times 10^5,T \leq 10 を満たすデータセットに正解した場合 10 点が与えられる。
  • N \leq 10^9,T \leq 10 を満たすデータセットに正解した場合追加で 10 点が与えられる。

入力

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

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

ここで \mathrm{Case}_i は i 番目のテストケースを意味する。それぞれのテストケースは以下の形式で与えられる。

N

出力

T 行出力せよ。i 行目には i 番目のテストケースに対する答えを出力せよ。

入力例 1

4
12
6
5839
123456

出力例 1

924
0
966252995
432934749

1 番目のテストケースでは、条件を満たす文字列は npcapcNPCAPC や NPCnpcAapPCc などの 924 通りがあります。

入力例 2

3
123456789
987654321
999999999

出力例 2

333574957
124462731
163251704