Problem Description

Bitaro works at a pancake shop.

The most popular menu item at this shop is a pancake tower consisting of $ N $ pancakes stacked on top of each other. There are three flavors of pancakes made at the shop, which we will refer to as A, B, and C.

Here, a pancake tower is called a good pancake tower if it satisfies the following conditions:

• For every pair of A and B flavored pancakes, the A flavored pancake is above the B flavored pancake.
• For every pair of A and C flavored pancakes, the A flavored pancake is above the C flavored pancake.
• For every pair of B and C flavored pancakes, the B flavored pancake is above the C flavored pancake.

For example, a pancake tower with flavors AABBBC, ACC, and BBBB from top to bottom are all good pancake towers, but AABABCC and CA are not.

Bitaro, who is in charge of plating, can perform the following operation on a pancake tower:

• Operation $ k $ ($2 \leq k \leq N$): Insert a spatula under the $ k $th pancake from the top and flip the top $ k $ pancakes. That is, reverse the order of the top $ k $ pancakes.

For example, if the flavors of the pancakes from top to bottom are ABCB, performing operations $ 2 $, $ 3 $, and $ 4 $ will result in BACB, CBAB, and BCBA respectively.

Now, there are $ Q $ plates of pancake towers, and the $ i $th plate ($1 \leq i \leq Q$) has the flavors $ S_{i,1}S_{i,2} \cdots S_{i,N} from top to bottom. Bitaro wants to make each pancake tower a good pancake tower with the fewest number of operations.

Given the arrangement information of the $ Q $ pancake towers, write a program to find the minimum number of operations required to make each pancake tower a good pancake tower.

Input Format

The input is given from the standard input in the following format:

$ N $ $ Q $ $ S_1 $ $ S_2 $ $\vdots$ $ S_Q $

Where $ S_i $ ($1 \leq i \leq Q$) is a string of length $ N $, and the $ j $th character ($1 \leq j \leq N$) is $ S_{i,j} $.

Output Format

Output $ Q $ lines to the standard output. The $ i $th line ($1 \leq i \leq Q$) should contain the minimum number of operations required to make the $ i $th pancake tower a good pancake tower.

Sample Input and Output

Sample Input #1

5 3
ABCBA
CCBAB
AAAAA

Sample Output #1

3
2
0

Sample Input #2

2 5
AC
AC
AC
AC
AC

Sample Output #2

0
0
0
0
0

Sample Input #3

13 1
ABCCABCBACBAA

Sample Output #3

9

Sample Input #4

13 4
CCAAACBAAAABB
BBBCCBCCCBCBC
CCCAAAABBBBBB
AABCBCACBACBA

Sample Output #4

4
6
2
10

Notes/Hints

Constraints

• $2 \leq N \leq 13$.
• $1 \leq Q \leq 100,000$.
• $ S_{i,j} $ is either A, B, or C ($1 \leq i \leq Q$, $1 \leq j \leq N$).

Subtasks

1. ($ 4 $ points) $N \leq 5$, $ Q = 1 $.
2. ($ 10 $ points) $N \leq 5$.
3. ($ 60 $ points) $ Q = 1 $.
4. ($ 26 $ points) No additional constraints.

Sample Explanation 1

For the first plate of pancakes, the following $ 3 $ operations can make it a good pancake tower:
1. Perform operation $ 4 $. The flavors are now BCBAA from top to bottom.
2. Perform operation $ 2 $. The flavors are now CBBAA from top to bottom.
3. Perform operation $ 5 $. The flavors are now AABBC from top to bottom.
It is impossible to make it a good pancake tower with $ 2 $ or fewer operations, so output $ 3 $ on the first line.

For the second plate of pancakes, the following $ 2 $ operations can make it a good pancake tower:
1. Perform operation $ 5 $. The flavors are now BABCC from top to bottom.
2. Perform operation $ 2 $. The flavors are now ABBCC from top to bottom.
It is impossible to make it a good pancake tower with $ 1 $ or fewer operations, so output $ 2 $ on the second line.

For the third plate of pancakes, it is already a good pancake tower, so no operations are needed. Therefore, output $ 0 $ on the third line.

Sample Explanation 2

Note that there may be multiple plates of pancakes with the same arrangement.

见题面 Input 部分

见题面 Output 部分