P14331 [JOI2021 预选赛 R2] 煎饼 / Pancake

比太郎在一家煎饼店工作。 该店最受欢迎的菜单是由 $ 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 $ 座煎饼塔变为良好煎饼塔所需的最少操作次数。

### 样例 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 完成