问题描述

太郎在一个薄煎饼店工作。

这家店最受欢迎的菜单是由N块煎饼叠放而成的煎饼塔。这家店制作的煎饼有三种口味，分别称为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} \cdots S_{i,N}$。对于每一个煎饼塔，太郎想要用尽可能少的操作次数将其变成好煎饼塔。

给定Q盘煎饼塔的排列信息，请编写一个程序，计算每个煎饼塔变成好煎饼塔所需的最小操作次数。

约束条件

• 2 ≤ N ≤ 13。
• 1 ≤ Q ≤ 100,000。
• $S_{i,j}$ 是字符'A'、'B'、'C'中的一个（1 ≤ i ≤ Q，1 ≤ j ≤ N）。

子任务

1. (4 分) N ≤ 5，Q = 1。
2. (10 分) N ≤ 5。
3. (60 分) Q = 1。
4. (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盘煎饼塔变成好煎饼塔所需的最小操作次数。

示例输入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