AT_arc179_f [ARC179F] All the Same

[problemUrl]: https://atcoder.jp/contests/arc179/tasks/arc179_f 文字 `A` `B` のみからなる長さ $ N $ の文字列 $ S $ が与えられます. 文字 `1` `2` `3` のみからなる長さ $ N $ の文字列 $ X $ に対して **スコア** を以下の手順によって定めます. > まず変数 $ h_1,h_2,h_3,P $ をそれぞれ $ 0 $ で初期化します. > > 次に $ i=1,2,\dots\ ,N $ の順に次の操作を行います. > > - $ S $ の $ i $ 文字目が `A` なら操作Aを, `B` なら操作Bを行う. ただし, $ X $ の $ i $ 文字目が表す数字を $ d $ とする. > > > - **操作A** : $ h_d $ に $ 2 $ を加算する. > - **操作B** : $ d=2 $ または $ h_d\neq\ h_2 $ のとき $ P $ を $ -10^{100} $ とする. そうでなければ $ h_d $ と $ h_2 $ にそれぞれ $ 1 $ を加算する. > - $ h_1=h_2=h_3 $ のとき $ P $ に $ 1 $ を加える. > > 最後に最終的な $ P $ をスコアとします. スコアを最大にする $ X $ を $ 1 $ つ出力してください. $ T $ 個のテストケースが与えられるので, それぞれについて解いてください.

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

$ T $ 行出力せよ. $ i\ (1\le\ i\le\ T) $ 行目には $ i $ 番目のテストケースにおけるスコアを最大にする文字列 $ X $ を $ 1 $ つ出力せよ. なお, スコアを最大にする $ X $ が複数存在する場合は, どれを出力しても正答となる.

### 制約 - $ 1\le\ T\le\ 10^5 $ - $ 1\le\ N\le\ 10^6 $ - $ S $ は `A` `B` のみからなる長さ $ N $ の文字列 - $ T,N $ は整数 - すべてのテストケースにおける $ N $ の総和は $ 10^6 $ 以下 ### Sample Explanation 1 手順で $ i=1,2,\dots\ ,N $ と進む際の $ (h_1,h_2,h_3,P) $ の変化を述べます. - $ 1 $ 番目のテストケースについて, $ (0,0,0,0)\rightarrow\ (2,0,0,0)\rightarrow\ (2,1,1,0)\rightarrow\ (2,2,2,1)\rightarrow\ (2,2,4,1) $ となります. スコアの最大値は $ 1 $ です. - $ 2 $ 番目のテストケースについて, $ (0,0,0,0)\rightarrow\ (2,0,0,0)\rightarrow\ (2,2,0,0)\rightarrow\ (2,2,2,1)\rightarrow\ (2,4,2,1)\rightarrow\ (4,4,2,1) $ となります. スコアの最大値は $ 1 $ です. $ 3,4,5 $ 番目のテストケースでは, スコアの最大値はそれぞれ $ 0,0,2 $ です. スコアが最大となる $ X $ は複数存在する可能性がありますが, そのうちの $ 1 $ つを出力してください.