팬케이크 (Pancake)

시간 제한2.5초메모리 제한1024 MB

요약

A, B, C 세 가지 맛으로 이루어진 N층 팬케이크 탑 Q개가 주어질 때, 위쪽부터 A, B, C 순서로 정렬된 좋은 탑이 되기 위한 최소 뒤집기 횟수를 각 탑마다 구한다.

난이도: 보통10점 중 7점
유형: BFS, 그리디, 비트 연산, 완전 탐색
정답자: 아직 제출이 없습니다

문제

비타로는 팬케이크 가게에서 일한다.

이 가게에서 가장 인기 있는 메뉴는 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)의 팬케이크 탑은 팬케이크의 맛이 위에서부터 순서대로 Si,1 Si,2 … Si,N이다. 비타로는 각각의 팬케이크 탑에 대해, 가능한 한 적은 횟수의 조작으로 좋은 팬케이크 탑으로 만들고 싶다.

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

입력

입력은 다음 형식으로 표준 입력에서 주어진다.

N Q
S1
S2
:
SQ

단, Si (1 ≦ i ≦ Q)는 길이 N의 문자열이고, 그 j번째 문자 (1 ≦ j ≦ N)는 Si,j이다.

출력

표준 출력에 Q행을 출력한다. i번째 행 (1 ≦ i ≦ Q)에는 i번째 접시의 팬케이크 탑에 대해 좋은 팬케이크 탑으로 만드는 데 필요한 조작 횟수의 최솟값을 출력한다.

제한

2 ≦ N ≦ 13.
1 ≦ Q ≦ 100 000.
Si,j는 A, B, C 중 하나이다 (1 ≦ i ≦ Q, 1 ≦ j ≦ N).

예제4

예제 1
입력
```
5 3
ABCBA
CCBAB
AAAAA
```
예상 출력
```
3
2
0
```
예제 2
입력
```
2 5
AC
AC
AC
AC
AC
```
예상 출력
```
0
0
0
0
0
```
예제 3
입력
```
13 1
ABCCABCBACBAA
```
예상 출력
```
9
```

예제 4

입력

13 4
CCAAACBAAAABB
BBBCCBCCCBCBC
CCCAAAABBBBBB
AABCBCACBACBA

예상 출력