AT_agc076_b [AGC076B] Split and Reverse

$ 0,1 $ からなる長さ $ N $ の整数列 $ X=(X_1,X_2,\cdots,X_N) $ が与えられます． あなたは以下の操作を $ 0 $ 回以上行うことができます． - $ X $ の各要素を `A` または `B` のグループに分類する． そして各グループに対して，そこに含まれる要素の順番を反転させる． より厳密に言えば，グループに含まれる要素が $ X_{i_1},X_{i_2},\cdots,X_{i_s} $ ( $ i_1

入力は以下の形式で標準入力から与えられる． > $ T $ $ case_1 $ $ case_2 $ $ \vdots $ $ case_T $ 各テストケースは以下の形式で与えられる． > $ N $ $ X_1 $ $ X_2 $ $ \cdots $ $ X_N $

各ケースについて，以下の形式で出力せよ． > $ k $ $ s_1 $ $ s_2 $ $ \vdots $ $ s_k $ ただしここで $ k $ は必要な最小の操作回数であり， $ s_i $ は $ i $ 回目の操作を表す文字列である． $ s_i $ は `A`,`B` からなる長さ $ N $ の文字列であり， $ s_i $ の $ j $ 文字目は， $ i $ 回目の操作で $ X_j $ を入れるグループを表す． 解が複数ある場合はどれを出力してもよい．

### Sample Explanation 1 $ 1 $ つ目のテストケースは，以下のように $ 2 $ 回の操作で目標を達成することができ，これが最小の操作回数です． - $ 1 $ 回目の操作: $ s_1 $ =`AABA` で操作する． $ (X_1,X_2,X_4) $ がグループ `A` に含まれるため，これらの順番を反転させ， $ (X_1,X_2,X_4)=(1,1,0) $ となる． 同様に， $ (X_3) $ がグループ `B` に含まれるため，これらの順番を反転させ， $ (X_3)=(0) $ となる． よって，全体では $ X=(1,1,0,0) $ となる． - $ 2 $ 回目の操作: $ s_2 $ =`BBBB` で操作する． $ () $ がグループ `A` に含まれるため，これらの順番を反転させ， $ ()=() $ となる． 同様に， $ (X_1,X_2,X_3,X_4) $ がグループ `B` に含まれるため，これらの順番を反転させ， $ (X_1,X_2,X_3,X_4)=(0,0,1,1) $ となる． よって，全体では $ X=(0,0,1,1) $ となる． $ 2 $ つ目のテストケースでは，操作を $ 0 $ 回行うことで目標を達成できます． ### Constraints - $ 1 \leq T \leq 250000 $ - $ 1 \leq N \leq 250000 $ - $ 0 \leq X_i \leq 1 $ - $ T $ ケースにわたる $ N $ の総和は $ 250000 $ 以下 - 入力はすべて整数