AT_joi2021_yo2_b パンケーキ (Pancake)

[problemUrl]: https://atcoder.jp/contests/joi2021yo2/tasks/joi2021_yo2_b ビ太郎はパンケーキ店で働いている． この店で最も人気のあるメニューは $ N $ 枚のパンケーキが積み重なったパンケーキタワーである．店で作られているパンケーキには $ 3 $ 種類の味があり，それぞれ `A`，`B`，`C` と呼ぶことにする． ここで，パンケーキの並び方が次の条件を満たすようになっているパンケーキタワーを**良いパンケーキタワー**と呼ぶことにする． - すべての味 `A` のパンケーキと味 `B` のパンケーキの組において，味 `A` のパンケーキが味 `B` のパンケーキより上にある． - すべての味 `A` のパンケーキと味 `C` のパンケーキの組において，味 `A` のパンケーキが味 `C` のパンケーキより上にある． - すべての味 `B` のパンケーキと味 `C` のパンケーキの組において，味 `B` のパンケーキが味 `C` のパンケーキより上にある． 例えば，パンケーキの味がそれぞれ上から順に `AABBBC`，`ACC`，`BBBB` となっているパンケーキタワーはどれも良いパンケーキタワーであるが，`AABABCC`，`CA` となっているパンケーキタワーはどれも良いパンケーキタワーではない． 盛り付け担当のビ太郎はパンケーキタワーに対して次の操作を行うことができる． - 操作 $ k $ ($ 2\ \leqq\ k\ \leqq\ N $)：上から $ k $ 枚目のパンケーキの下側にフライ返しを差し込み，そこから上のパンケーキをひっくり返す．すなわち，上から $ k $ 枚のパンケーキの並び方を反転させる． 例えば，パンケーキの味が上から順に `ABCB` となっているパンケーキタワーに操作 $ 2 $，操作 $ 3 $，操作 $ 4 $ をそれぞれ行った場合，パンケーキの並び方は `BACB`，`CBAB`，`BCBA` となる． 今，$ Q $ 皿のパンケーキタワーがあり，$ i $ 皿目 ($ 1\ \leqq\ i\ \leqq\ Q $) のパンケーキタワーはパンケーキの味が上から順に $ S_{i,1}S_{i,2}\ \cdots\ S_{i,N} $ となっている．ビ太郎はそれぞれのパンケーキタワーについて，できる限り少ない回数の操作で良いパンケーキタワーにしたい． $ Q $ 皿のパンケーキタワーの並び方の情報が与えられるので，それぞれのパンケーキタワーについて，良いパンケーキタワーにするのに必要な操作の回数の最小値を求めるプログラムを作成せよ．

入力は以下の形式で標準入力から与えられる． > $ N $ $ Q $ $ S_1 $ $ S_2 $ $ \vdots $ $ S_Q $ ただし，$ S_i $ ($ 1\ \leqq\ i\ \leqq\ Q $) は長さ $ N $ の文字列で，その $ j $ 文字目 ($ 1\ \leqq\ j\ \leqq\ N $) は $ S_{i,j} $ である．

標準出力に $ Q $ 行出力せよ．$ i $ 行目 ($ 1\ \leqq\ i\ \leqq\ Q $) には，$ i $ 皿目のパンケーキタワーについて，良いパンケーキタワーにするのに必要な操作の回数の最小値を出力せよ．

### 制約 - $ 2\ \leqq\ N\ \leqq\ 13 $． - $ 1\ \leqq\ Q\ \leqq\ 100\,000 $． - $ S_{i,j} $ は `A`，`B`，`C` のいずれかである ($ 1\ \leqq\ i\ \leqq\ Q $，$ 1\ \leqq\ j\ \leqq\ N $)． ### 小課題 1. ($ 4 $ 点) $ N\ \leqq\ 5 $，$ Q\ =\ 1 $． 2. ($ 10 $ 点) $ N\ \leqq\ 5 $． 3. ($ 60 $ 点) $ Q\ =\ 1 $． 4. ($ 26 $ 点) 追加の制約はない． ### Sample Explanation 1 $ 1 $ 皿目のパンケーキタワーの場合，以下の $ 3 $ 回の操作を行うことによって良いパンケーキタワーにすることが可能である． 1. 操作 $ 4 $ を行う．パンケーキの味は上から順に `BCBAA` となる． 2. 操作 $ 2 $ を行う．パンケーキの味は上から順に `CBBAA` となる． 3. 操作 $ 5 $ を行う．パンケーキの味は上から順に `AABBC` となる． $ 2 $ 回以下の操作によって良いパンケーキタワーにすることは不可能であるので，$ 1 $ 行目に $ 3 $ を出力する． $ 2 $ 皿目のパンケーキタワーの場合，以下の $ 2 $ 回の操作を行うことによって良いパンケーキタワーにすることが可能である． 1. 操作 $ 5 $ を行う．パンケーキの味は上から順に `BABCC` となる． 2. 操作 $ 2 $ を行う．パンケーキの味は上から順に `ABBCC` となる． $ 1 $ 回以下の操作によって良いパンケーキタワーにすることは不可能であるので，$ 2 $ 行目に $ 2 $ を出力する． $ 3 $ 皿目のパンケーキタワーの場合，既に良いパンケーキタワーになっているので操作を行う必要がない．したがって，$ 3 $ 行目に $ 0 $ を出力する． ### Sample Explanation 2 パンケーキの並び方が同じであるようなパンケーキタワーが複数個存在する場合もあることに注意せよ．