该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

小A同学在煎饼店工作，这里的煎饼塔很受欢迎。煎饼塔由A,B,C三种煎饼组成。其中煎饼的口味的顺序

是A>B>C。

任何从上到下按煎饼口味顺序排列的煎饼塔都是好的煎饼塔。例如AABBC是好的煎饼塔，AABCB是不好

的煎饼塔。

负责摆盘的小A可以对煎饼塔进行以下操作

操作k(2≤k≤N):在从上面数第k张煎饼的下方插入飞铲，从那里翻转上面的煎饼，即从上面翻转k张煎

饼的排列方法

例如，对煎饼的味道从上到下依次为ABCB的煎饼塔进行操作3时，煎饼的排列方式为CBAB。

现在有Q盘煎饼塔，小A对于各个煎饼塔，希望尽可能的用较少的次数来操作，使其成为好的煎饼塔。

给出Q盘煎饼塔的信息，请编写程序求出每盘煎饼塔所需的操作次数的最小值。

Format

Input

第一行输入两个整数N Q,表示煎饼塔的大小和数量

接下来 行 个字符，第 i 行 第 j 个字符表示第 i 个煎饼塔第 j 个煎饼的口味 .

Output

输出Q行，每行一个整数，表示煎饼塔所需的最小操作次数。

Samples

5 3 
ABCBA 
CCBAB 
AAAAA

3 
2 
0

对于 ABCBA

执行操作4得到BCBAA

执行操作2得到CBBAA

执行操作5得到AABBC

13 1 
ABCCABCBACBAA

9

Limitation

约束

• $2\leq N \leq 13$
• $1\leq Q \leq 100000$
• $S_{ij}为A，B或C$

数据范围