팬케이크

문제

비타로는 팬케이크 가게에서 일하고 있다.

이 가게에서 가장 인기 있는 메뉴는 $N$ 장의 팬케이크가 쌓여 있는 팬케이크 타워이다. 가게에서 만들어지는 팬케이크에는 $3$ 가지 맛이 있으며, 각각 A, B, C 라고 부르기로 한다.

여기서 팬케이크의 배열이 다음 조건을 만족하는 팬케이크 타워를 좋은 팬케이크 타워라고 부르기로 한다.

• 모든 맛 A 의 팬케이크와 맛 B 의 팬케이크 쌍에 대하여, 맛 A 의 팬케이크가 맛 B 의 팬케이크보다 위에 있다.
• 모든 맛 A 의 팬케이크와 맛 C 의 팬케이크 쌍에 대하여, 맛 A 의 팬케이크가 맛 C 의 팬케이크보다 위에 있다.
• 모든 맛 B 의 팬케이크와 맛 C 의 팬케이크 쌍에 대하여, 맛 B 의 팬케이크가 맛 C 의 팬케이크보다 위에 있다.

예를 들어 팬케이크의 맛이 각각 위에서부터 순서대로 AABBBC, ACC, BBBB 인 팬케이크 타워는 모두 좋은 팬케이크 타워이지만, AABABCC, CA 인 팬케이크 타워는 모두 좋은 팬케이크 타워가 아니다.

담기 담당인 비타로는 팬케이크 타워에 대하여 다음 조작을 할 수 있다.

• 조작 $k$ ($2 \le k \le N$): 위에서 $k$ 번째 팬케이크의 아래쪽에 뒤집개를 넣어, 거기서부터 위에 있는 팬케이크를 뒤집는다. 즉, 위에서 $k$ 장의 팬케이크의 배열을 반전시킨다.

예를 들어 팬케이크의 맛이 위에서부터 순서대로 ABCB 인 팬케이크 타워에 조작 $2$, 조작 $3$, 조작 $4$ 를 각각 수행한 경우, 팬케이크의 배열은 BACB, CBAB, BCBA 가 된다.

지금 $Q$ 접시의 팬케이크 타워가 있으며, $i$ 번째 접시 ($1 \le i \le Q$) 의 팬케이크 타워는 팬케이크의 맛이 위에서부터 순서대로 $S_{i,1} S_{i,2} \dots S_{i,N}$ 이다. 비타로는 각각의 팬케이크 타워에 대하여 가능한 한 적은 횟수의 조작으로 좋은 팬케이크 타워로 만들고 싶다.

$Q$ 접시의 팬케이크 타워의 배열 정보가 주어지므로, 각각의 팬케이크 타워에 대하여 좋은 팬케이크 타워로 만드는 데 필요한 조작 횟수의 최솟값을 구하는 프로그램을 작성하시오.

제한

• $2 \le N \le 13$.
• $1 \le Q \le 100\,000$.
• $S_{i,j}$ 는 A, B, C 중 하나이다 ($1 \le i \le Q$, $1 \le j \le N$).

서브태스크

1. ($4$ 점) $N \le 5$, $Q = 1$.
2. ($10$ 점) $N \le 5$.
3. ($60$ 점) $Q = 1$.
4. ($26$ 점) 추가 제약이 없다.

입력

입력은 다음 형식으로 표준 입력에서 주어진다.
$N$ $Q$
$S_{1}$
$S_{2}$
$:$
$S_{Q}$

단, $S_{i}$ ($1 \le i \le Q$) 는 길이 $N$ 의 문자열이며, 그 $j$ 번째 문자 ($1 \le j \le N$) 는 $S_{i,j}$ 이다.

출력

표준 출력에 $Q$ 줄을 출력한다. $i$ 번째 줄 ($1 \le i \le 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