题目描述

灰灰去游戏厅打游戏,获得了一串游戏机彩票(所以保证所有彩票一定连号),每张彩票只会写有字面A或者B.

这家游戏厅的老板比较喜欢做puzzle,所以连兑换彩票都有特别的规则.

彩票兑换共有两条规则,规则如下

• 选择两张连号的彩票AB, 将其内容改为BC, 你就可以得到一枚游戏币.
• 选择两张连号彩票BA, 内容改为CB, 然后你可以得到一枚游戏币.

所以灰灰请你帮帮他兑换最多的游戏币！

输入格式

输入包含多组数据.

第一行包含一个整数t ($1≤t≤1000$) — 代表数据的组数.

每组数据只包含一行字符串 s($~1~≤~|s|~≤~2~\times~10^5$). 且字符串所有字母仅为A或B

保证所有数据字符串长度之和不超过 $2~\times~10^5$ .

输出格式

对于每组数据, 输出一个整数 — 代表灰灰最多能兑换的游戏币.

input

8
ABBA
ABA
BAABA
ABB
AAAAAAB
BABA
B
AAA

output

2
1
3
1
6
2
0
0

样例说明

在第一组测试数据中 你可以通过做下面的操作获取两个游戏币：

ABBA → BCBA → BCCB

在第二组测试数据中，你可以通过做下面的操作获得一个游戏币：

ABA→BCA

第三组数据中，你可以做下面的操作或者三个游戏币

BAABA→CBABA→CBACB→CCBCB

数据范围

对于100%数据满足, $1≤t≤1000, ~1~≤~|s|~≤~2~\times~10^5,~ s_i\in\{'A','B'\} $