레이팅 미적용ビ太郎はパンケーキ店で働いている.
この店で最も人気のあるメニューは 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 ).
( 4 点) N ≦ 5 , Q = 1 .
( 10 点) N ≦ 5 .
( 60 点) Q = 1 .
( 26 点) 追加の制約はない.
入力は以下の形式で標準入力から与えられる.
N Q
S 1
S 2
:
S Q
ただし, S i ( 1 ≦ i ≦ Q ) は長さ N の文字列で,その j 文字目 ( 1 ≦ j ≦ N ) は S i,j である.
標準出力に Q 行出力せよ. i 行目 ( 1 ≦ i ≦ Q ) には, i 皿目のパンケーキタワーについて,良いパンケーキタワーにするのに必要な操作の回数の最小値を出力せよ.
5 3
ABCBA
CCBAB
AAAAA
3
2
0
2 5
AC
AC
AC
AC
AC
0
0
0
0
0
13 1
ABCCABCBACBAA
9
13 4
CCAAACBAAAABB
BBBCCBCCCBCBC
CCCAAAABBBBBB
AABCBCACBACBA
4
6
2
10