题目内容

调度台连续下发若干条长度为 L 的档位串。每条串只由大写字母 A、B、C 组成，分别表示低、中、高三档。手册要求把档位整理成「低档在前、高档在后」，也就是所有 A 都出现在所有 B、C 之前，所有 B 都出现在所有 C 之前。

每次操作只能选当前串的一个前缀并整体反转。值班同学要对每条串求出最少操作次数。长度为 1 的前缀反转不改变串，因此只需考虑长度至少为 2 的前缀。

共有 T 条待整理的串，长度都是 L。对每条串单独输出答案。

约束：2 $\le$ L $\le$ 13，1 $\le$ T $\le$ $10^5$。

输入描述

第一行两个正整数 L、T（2 $\le$ L $\le$ 13，1 $\le$ T $\le$ $10^5$），表示串长与串的条数。

接下来 T 行，每行一个长度为 L、仅含 A、B、C 的字符串。

输出描述

对每个字符串输出一行一个整数，表示最少前缀反转次数。

样例1

输入

3 2
BAC
CBA

输出

1
1

说明

• BAC 反转长度为 2 的前缀得到 ABC，已经有序，故 1 次。
• CBA 反转整段得到 ABC，故 1 次。

样例2

输入

5 2
CCBAB
ABCBA

输出

2
3

说明

• CCBAB 可先翻整段得到 BABCC，再翻长度为 2 的前缀得到 ABBCC，共 2 次。
• ABCBA 最少需要 3 次才能变成 AABBC。