题目描述

月底了，文文没有钱了，涛涛要跟文文玩一个游戏

文文将得到一个由”A”和”B”组成的字符串s。 


涛涛告诉文文可以执行以下两种操作：


1. 选择一个子串AB，将其更改为BC，然后得到一块钱。 


2. 选择一个子串BA，将其更改为CB，然后得到一块钱。 


问文文最多能得到多少钱？

输入格式

该输入由多个测试用例组成。

第一行包含一个整数t（1 ≤ t ≤ 1000）表示测试用例的数量。 


每个测试用例包含字符串s（1 ≤ |s| ≤ 2e5）。


题目保证字符串s仅由”A” 和 ”B”组成， 所有测试用例中的 s 的长度之和不超过 2e5。

输出格式

对于每个测试用例，输出一个整数表示文文最多拿到多少钱

8
ABBA
ABA
BAABA
ABB
AAAAAAB
BABA
B
AAA

2
1
3
1
6
2
0
0

提示

在第一个样例中你可以通过以下方式得到2个金币 ABBA→BCBA→BCCB

在第二个样例中你可以通过以下方式得到1个金币 ABA→BCA