第20回日本情報オリンピック　二次予選

2020年12月14日
情報オリンピック日本委員会

問題文

ビ太郎はパンケーキ店で働いている．

この店で最も人気のあるメニューは N 枚のパンケーキが積み重なったパンケーキタワーである．店で作られているパンケーキには 3 種類の味があり，それぞれ A，B，C と呼ぶことにする．

ここで，パンケーキの並び方が次の条件を満たすようになっているパンケーキタワーを良いパンケーキタワーと呼ぶことにする．

• すべての味 A のパンケーキと味 B のパンケーキの組において，味 A のパンケーキが味 B のパンケーキより上にある．
• すべての味 A のパンケーキと味 C のパンケーキの組において，味 A のパンケーキが味 C のパンケーキより上にある．
• すべての味 B のパンケーキと味 C のパンケーキの組において，味 B のパンケーキが味 C のパンケーキより上にある．

例えば，パンケーキの味がそれぞれ上から順に AABBBC，ACC，BBBB となっているパンケーキタワーはどれも良いパンケーキタワーであるが，AABABCC，CA となっているパンケーキタワーはどれも良いパンケーキタワーではない．

盛り付け担当のビ太郎はパンケーキタワーに対して次の操作を行うことができる．

• 操作 k (2 ≦ k ≦ N)：上から k 枚目のパンケーキの下側にフライ返しを差し込み，そこから上のパンケーキをひっくり返す．すなわち，上から k 枚のパンケーキの並び方を反転させる．

例えば，パンケーキの味が上から順に ABCB となっているパンケーキタワーに操作 2，操作 3，操作 4 をそれぞれ行った場合，パンケーキの並び方は BACB，CBAB，BCBA となる．

今，Q 皿のパンケーキタワーがあり，i 皿目 (1 ≦ i ≦ Q) のパンケーキタワーはパンケーキの味が上から順に S_i,1 S_i,2 … S_i,N となっている．ビ太郎はそれぞれのパンケーキタワーについて，できる限り少ない回数の操作で良いパンケーキタワーにしたい．

Q 皿のパンケーキタワーの並び方の情報が与えられるので，それぞれのパンケーキタワーについて，良いパンケーキタワーにするのに必要な操作の回数の最小値を求めるプログラムを作成せよ．

制約

• 2 ≦ N ≦ 13．
• 1 ≦ Q ≦ 100 000．
• S_i,j は A，B，C のいずれかである (1 ≦ i ≦ Q，1 ≦ j ≦ N)．

小課題

1. (4 点) N ≦ 5，Q = 1．
2. (10 点) N ≦ 5．
3. (60 点) Q = 1．
4. (26 点) 追加の制約はない．

入力

入力は以下の形式で標準入力から与えられる．
N Q
S₁
S₂
:
S_Q

ただし，S_i (1 ≦ i ≦ Q) は長さ N の文字列で，その j 文字目 (1 ≦ j ≦ N) は S_i,j である．

出力

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

入出力例

入力例 1
5 3
ABCBA
CCBAB
AAAAA

出力例 1
3
2
0

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 を出力する．

入力例 2
2 5
AC
AC
AC
AC
AC

出力例 2
0
0
0
0
0

パンケーキの並び方が同じであるようなパンケーキタワーが複数個存在する場合もあることに注意せよ．

入力例 3
13 1
ABCCABCBACBAA

出力例 3
9

入力例 4
13 4
CCAAACBAAAABB
BBBCCBCCCBCBC
CCCAAAABBBBBB
AABCBCACBACBA

出力例 4
4
6
2
10