Ex - TGC Triplets

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

操作

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

個のテストケースが与えられます．
個目のテストケースでは， として次の問題を解いてください．

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

• は整数
• は A, T, G, C, U のみからなる長さ の文字列

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

行出力せよ．
行目には 個目のテストケースに対する答えを出力せよ．

3
4
CTGC
3
AGC
3
GCC

20
10
8

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

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