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
の 通りあります.
で割ったあまりを出力することを忘れないようにしてください.