#joi2021yo2b. [joi2021_yo2_b]パンケーキ (Pancake)

[joi2021_yo2_b]パンケーキ (Pancake)

问题描述

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

这家店最受欢迎的菜单是由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) 的煎饼塔的口味依次从上到下是Si,1Si,2Si,NS_{i,1}S_{i,2} \cdots S_{i,N}。对于每一个煎饼塔,太郎想要用尽可能少的操作次数将其变成好煎饼塔。

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

约束条件

  • 2 ≤ N ≤ 13。
  • 1 ≤ Q ≤ 100,000。
  • Si,jS_{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


示例输入4

13 4
CCAAACBAAAABB
BBBCCBCCCBCBC
CCCAAAABBBBBB
AABCBCACBACBA

示例输出4

4
6
2
10