题目描述

比太郎在一家煎饼店工作。

该店最受欢迎的菜单是由 $N$ 张煎饼堆叠而成的煎饼塔。店中制作的煎饼共有三种口味，分别称为 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} \cdots S_{i,N}$。比太郎希望对每一座煎饼塔，用尽可能少的操作次数将其变为良好煎饼塔。

给定 $Q$ 座煎饼塔的口味排列信息，请编写程序，求出每座煎饼塔变为良好煎饼塔所需的最少操作次数。

输入格式

输入通过标准输入以如下格式给出：

$N$ $Q$

$S_1$

$S_2$

$\vdots$

$S_Q$

其中，$S_i$（$1 \le i \le Q$）是一个长度为 $N$ 的字符串，其第 $j$ 个字符（$1 \le j \le N$）为 $S_{ij}$。

输出格式

在标准输出中输出 $Q$ 行。第 $i$ 行（$1 \le i \le 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

提示

样例 1 解释

对于第 1 座煎饼塔，通过执行以下 3 次操作，可以将其变为良好煎饼塔：

1. 执行操作 4，煎饼口味从上至下变为 BCBA A。
2. 执行操作 2，煎饼口味从上至下变为 CBBA A。
3. 执行操作 5，煎饼口味从上至下变为 AABBC。

无法通过 2 次或更少的操作将其变为良好煎饼塔，因此在第 1 行输出 3。

对于第 2 座煎饼塔，通过执行以下 2 次操作，可以将其变为良好煎饼塔：

1. 执行操作 5，煎饼口味从上至下变为 BABCC。
2. 执行操作 2，煎饼口味从上至下变为 ABBCC。

无法通过 1 次或更少的操作将其变为良好煎饼塔，因此在第 2 行输出 2。

对于第 3 座煎饼塔，其本身已是良好煎饼塔，无需执行任何操作。因此，在第 3 行输出 0。

数据范围

• $2 \le N \le 13$。
• $1 \le Q \le 100\,000$。
• $S_{ij}$ 为 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 分）无额外约束。

翻译由 Qwen3-235B 完成