Zookeeper 正在玩游戏。在这个游戏中,Zookeeper 必须使用炸弹来轰炸由字母“A”和“B”组成的字符串。他可以使用炸弹来轰炸“AB”或“BB”的子字符串。当他轰炸这样的子字符串时,该子字符串将从字符串中删除,并且字符串的其余部分被连接起来。
例如,Zookeeper 可以使用两个这样的操作:AABABBA $$$\to$$$ AABBA $$$\to$$$ AAA。
动物园管理员想知道他能制作的最短字符串是多少。你能帮他找出最短绳子的长度吗?
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ $$$(1 \leq t \leq 20000)$$$ — 测试用例的数量。测试用例的描述如下。
接下来的每一行 $$$t$$$ 都包含一个测试用例,由一个非空字符串 $$$s$$$ 组成:Zookeeper 需要轰炸的字符串。保证 $$$s$$$ 的所有符号都是 'A' 或 'B'。
保证所有测试用例中$$$|s|$$$($$$s$$$的长度)之和不超过$$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数:Zookeeper 可以生成的最短字符串的长度。
示例
输入 #1
3 AAA BABA AABBBABBBB
输出 #1
3 2 0
注意
对于第一个测试用例,您无法进行任何移动,因此答案是 $$$3$$$。
对于第二个测试用例,一个最佳的移动顺序是 BABA $$$\to$$$ BA。所以,答案是$$$2$$$。
对于第三个测试用例,最佳的移动顺序是 AABBBABBBB $$$\to$$$ AABBBABB $$$\to$$$ AABBBB $$$\to$$$ ABBB $$$\to$$$ AB $$$\to$$$ (空字符串)。所以,答案是$$$0$$$。