← 返回题目列表

Codeforces · 1428/C

C. A加三个B

中文机器翻译题面 查看原题

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$$$。