题目描述

最近黄老师到徐老师家做客，但是没想到机器人的控制器居然被徐老师放在了沙发上

于是黄老师一屁股坐在了控制器上，在黄老师做完客离开家里以后

徐老师发现机器人被输入了一连串的指令！

但是幸好的是，机器人收到的指令中只有两种指令：充电(C) 和 移动(M)

这让徐老师相当心疼，因为机器人进行移动是会导致磨损的！

而徐老师当然可以擦除机器人现在收到的指令序列，但是擦除指令也会对机器人造成损伤！

机器人现在的指令序列可以用一个仅包含 $C$ 和 $M$ 的字符串表示

由于随机擦除指令会极大的影响机器人的 $CPU$ 使用寿命，所以徐老师只会从指令序列的开头或者结尾擦除指令，不会擦除中间的指令

即如果指令序列为 $CCMMCC$，徐老师可以擦除开头的指令变成 $CMMCC,MMCC,MCC \dots$ 可以擦除结尾的指令变成 $CCMMC,CCMM,CCM,CC \dots$，也可以两段都擦除一部分变成 $CMMC,MM,M \dots$，当然也可以不擦除任何命令

这样可以让徐老师擦除指令时对机器人的损伤达到最小，但是不可避免的损伤依旧存在两种：

1. 擦除指令时，每擦除一个 $C$ 指令会对机器人造成 $1$ 点 $CPU$ 损伤
2. 剩余的指令集中，每存在一个 $M$ 指令会对机器人造成 $1$ 点物理损伤

徐老师只会关心两种损伤中比较大的损伤是多少

现在徐老师想知道，对于一个指令序列，怎么擦除指令可以使得机器人最终受到的损伤最小？

输入格式

第一行包含一个整数 $T$ 表示有多组测试数据

对于每组测试数据包含一行仅由大写字母 $C,M$ 组成的字符串，其中 $C$ 代表充电指令，$M$ 代表移动指令

输出格式

对于每组测试数据，输出一行包含一个整数表示最小的损伤

数据范围

数据点编号	字符串长度 $len$	其他
$1 \sim 3$	$1 \leq len \leq 100$	无
$4 \sim 5$	$1 \leq len \leq 20000$	每个指令序列中不超过 $10$ 个 $C$
$6 \sim 7$		每个指令序列中不超过 $10$ 个 $M$
$8 \sim 10$		无

对于 $100\%$ 的数据保证，$1 \leq T \leq 10$

样例输入1

5
CMCCCMCCM
CMMCMMCMMCMMC
MMMMCCCCCC
MMMMM
CCCC

样例输出1

1
3
0
0
0

样例解释1

第一组测试数据：$CMCCCMCCM \rightarrow (CM)CCCMCC(M)$ 移除的 $C$ 有 $1$ 个，剩余的 $M$有 $1$ 个，损伤为 $max(1,1)=1$

第二组测试数据：$CMMCMMCMMCMMC \rightarrow (CMMCMM)CMMC(MMC)$ 移除的 $C$ 有 $3$ 个，剩余的 $M$有 $2$ 个，损伤为 $max(3,2)=3$

第三组测试数据：$MMMMCCCCCC -> (MMMM)CCCCCC$ 移除的 $C$ 有 $0$ 个，剩余的 $M$ 有 $0$ 个，损伤为 $max(0,0)=0$

第四组测试数据：$MMMMM -> (MMMMM)$ 移除的 $C$ 有 $0$ 个，剩余的 $M$ 有 $0$ 个，损伤为 $max(0,0)=0$

第五组测试数据：$CCCC -> CCCC$ 移除的 $C$ 有 $0$ 个，剩余的 $M$ 有 $0$ 个，损伤为 $max(0,0)=0$

以上对于每组测试数据均只提供一种可能方案，方案可能不止一种