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 自动生成**