問題文

A, C, G, T, U からなる文字列に対して,以下に示す操作を繰り返し行うことができます.

操作

  • 以下のうちいずれかを行う
    • ある 11 文字であって A となっているものを T もしくは U で置き換える
    • ある 11 文字であって C となっているものを G で置き換える
    • ある 11 文字であって G となっているものを C で置き換える
    • ある 11 文字であって T となっているものを A で置き換える
    • ある 11 文字であって U となっているものを A, T, G, C のいずれかで置き換える
    • ある連続する 33 文字であって TGC となっているものを AC で置き換える

TT 個のテストケースが与えられます.
t(1tT)t \scriptsize \hspace{0.3em} (1 \leq t \leq T) 個目のテストケースでは,N=Nt,S=StN = N_t, S=S_t として次の問題を解いてください.

  • 長さ NN の文字列 SS に対して操作00 回以上好きなだけ行えるとき,操作後の文字列であって,長さが最小となるものは何通りあるか?
  • 求めよ.
  • 答えは非常に大きくなる場合があるため,998244353998244353 で割ったあまりを答えよ.

制約

  • 1T1041 \leq T \leq 10^4
  • 1St2×105(1tT)1 \leq |S_t| \leq 2 \times 10^5 \scriptsize \hspace{0.3em} (1 \leq t \leq T)
  • T,Nt(1tT)T, N_t \scriptsize \hspace{0.3em} (1 \leq t \leq T) は整数
  • StS_tA, T, G, C, U のみからなる長さ NtN_t の文字列 (1tT)\scriptsize \hspace{0.3em} (1 \leq t \leq T)
  • 1tTSt106\sum \limits_{1 \leq t \leq T} |S_t| \leq 10^6

入力

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

TT
N1N_1
S1S_1
N2N_2
S2S_2
\vdots
NTN_T
STS_T

出力

TT 行出力せよ.
t(1tT)t \scriptsize \hspace{0.3em} (1 \leq t \leq T) 行目には tt 個目のテストケースに対する答えを出力せよ.

サンプル

入力例1
3
4
CTGC
3
AGC
3
GCC
出力例
20
10
8

文字列 CTGC に対して適切に操作を行うことで,操作後の文字列の長さを 33 にすることができます.
どのように操作を行っても 33 未満にはできないので,これが最小です.
操作によって達成できる文字列であって,長さが 33 のものは CAC, CAG, CCC, CCG, CGC, CGG, CTC, CTG, CUC, CUG, GAC, GAG, GCC, GCG, GGC, GGG, GTC, GTG, GUC, GUG2020 通りあります.

998244353998244353 で割ったあまりを出力することを忘れないようにしてください.

Submit


Go (1.21)