AT_npcapc_2024_a Welcome to NPCAPC

英大文字と英小文字からなる長さ $ N $ の文字列のうち、 `NPCAPC` と `npcapc` の両方を部分文字列(連続でなくてもよい)として含むものの個数を $ 998244353 $ で割ったあまりを求めてください。 $ T $ 個のテストケースが与えられるので、それぞれについて解いてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \mathrm{Case}_1 $ $ \mathrm{Case}_2 $ $ \vdots $ $ \mathrm{Case}_T $ ここで $ \mathrm{Case}_i $ は $ i $ 番目のテストケースを意味する。それぞれのテストケースは以下の形式で与えられる。 > $ N $

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

### 部分点 この問題には複数の部分点が設定されている。 - $ N \leq 2\times 10^5,T \leq 10 $ を満たすデータセットに正解した場合 $ 10 $ 点が与えられる。 - $ N \leq 10^9,T \leq 10 $ を満たすデータセットに正解した場合追加で $ 10 $ 点が与えられる。 ### Sample Explanation 1 $ 1 $ 番目のテストケースでは、条件を満たす文字列は `npcapcNPCAPC` や `NPCnpcAapPCc` などの $ 924 $ 通りがあります。 ### Constraints - $ 1 \leq N\leq 10^9 $ - $ 1 \leq T\leq 5000 $