AT_joi2021_yo2_b.パンケーキ (Pancake)

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

这家店里最受欢迎的菜单是一座由 $N$ 个煎饼叠成的煎饼塔。店中供应的煎饼有三种口味，分别是 A、B 和 C。

如果煎饼的排列满足以下条件，我们就称其为好的煎饼塔：

• 所有 A 口味的煎饼必须位于 B 口味煎饼之上。
• 所有 A 口味的煎饼必须位于 C 口味煎饼之上。
• 所有 B 口味的煎饼必须位于 C 口味煎饼之上。

例如，若从上到下口味依次为 AABBBC、ACC、BBBB 的煎饼塔都符合是好煎饼塔的条件，但 AABABCC 和 CA 则不符合。

ビ太郎可以对煎饼塔进行以下操作：

• 操作 $k$ ($2 \leqq k \leqq N$)：将铲子插入第 $k$ 个煎饼下，翻转其上方的所有煎饼，即从上到下前 $k$ 个煎饼的顺序被反转。

例如，若煎饼塔的顺序为 ABCB，通过执行操作 $2$、操作 $3$ 和操作 $4$，其顺序将变为 BACB、CBAB 和 BCBA。

现在有 $Q$ 盘煎饼塔，给出每一盘煎饼从上到下的口味顺序为字符串 $S_{i,1}S_{i,2}\cdots S_{i,N}$。ビ太郎想通过尽量少的操作次数，让每一盘煎饼塔都变为好煎饼塔。

请编写程序，计算每一盘煎饼塔变为好煎饼塔所需的最少操作次数。

输入数据从标准输入中获取：

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

其中，$S_i$ ($1 \leqq i \leqq Q$) 是长度为 $N$ 的字符串，表示第 $i$ 盘煎饼塔的口味顺序。

输出结果到标准输出，每行表示一盘煎饼塔变为好煎饼塔所需的最少操作次数。

• $2 \leqq N \leqq 13$。
• $1 \leqq Q \leqq 100,000$。
• $S_{i,j}$ 是 A、B，或 C ($1 \leqq i \leqq Q$，$1 \leqq j \leqq N$)。

子任务

1. ($4$ 分) $N \leqq 5$，$Q = 1$。
2. ($10$ 分) $N \leqq 5$。
3. ($60$ 分) $Q = 1$。
4. ($26$ 分) 无其他约束。

样例解释

1. 对于第 1 盘煎饼塔，经过以下 3 次操作可以变为好煎饼塔：

   • 操作 4 后顺序为 BCBAA。
   • 操作 2 后顺序为 CBBAA。
   • 操作 5 后顺序为 AABBC。

   通过 $2$ 次或更少的操作无法达成，因此输出 $3$。

2. 对于第 2 盘煎饼塔，以下 2 次操作即可：

   • 操作 5 后顺序为 BABCC。
   • 操作 2 后顺序为 ABBCC。

   不能通过 1 次或更少的操作实现，因此输出 $2$。

3. 第 3 盘煎饼塔已经是好煎饼塔，无需操作，因此输出 $0$。

注意，有可能存在多盘煎饼塔的初始顺序相同的情况。

本翻译由 AI 自动生成