問題文

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

この店で最も人気のあるメニューは 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 皿のパンケーキタワーの並び方の情報が与えられるので，それぞれのパンケーキタワーについて，良いパンケーキタワーにするのに必要な操作の回数の最小値を求めるプログラムを作成せよ．

制約

• 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 点) 追加の制約はない．

入力例 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