CF1428C.ABBB

Zookeeper is playing a game. In this game, Zookeeper must use bombs to bomb a string that consists of letters 'A' and 'B'. He can use bombs to bomb a substring which is either "AB" or "BB". When he bombs such a substring, the substring gets deleted from the string and the remaining parts of the string get concatenated.

For example, Zookeeper can use two such operations: AABABBA $\to$ AABBA $\to$ AAA.

Zookeeper wonders what the shortest string he can make is. Can you help him find the length of the shortest string?

动物园管理员正在玩一个游戏。在该游戏中，动物园管理员必须使用炸弹来轰炸一个仅由字母 'A' 和 'B' 组成的字符串。他可以使用炸弹轰炸形如 "AB" 或 "BB" 的子串；当轰炸这样的子串时，该子串将从原字符串中被删除，而字符串剩余部分则会连接在一起。

例如，动物园管理员可以执行如下两次操作：AABABBA $\to$ AABBA $\to$ AAA。

动物园管理员想知道他能得到的最短字符串是什么。你能帮他找出该最短字符串的长度吗？

Each test contains multiple test cases. The first line contains a single integer $t$ $(1 \leq t \leq 20000)$ — the number of test cases. The description of the test cases follows.

Each of the next $t$ lines contains a single test case each, consisting of a non-empty string $s$: the string that Zookeeper needs to bomb. It is guaranteed that all symbols of $s$ are either 'A' or 'B'.

It is guaranteed that the sum of $|s|$ (length of $s$) among all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 20000$），表示测试用例的数量。随后是各测试用例的描述。

接下来的 $t$ 行中，每行包含一个测试用例，即一个非空字符串 $s$：这是动物园管理员需要“轰炸”的字符串。保证字符串 $s$ 中的所有字符均为 'A' 或 'B'。

保证所有测试用例中 $|s|$（即字符串 $s$ 的长度）之和不超过 $2 \cdot 10^5$。

For each test case, print a single integer: the length of the shortest string that Zookeeper can make.

对于每个测试用例，输出一个整数：Zookeeper 能够构造的最短字符串的长度。

For the first test case, you can't make any moves, so the answer is $3$.

For the second test case, one optimal sequence of moves is BABA $\to$ BA. So, the answer is $2$.

For the third test case, one optimal sequence of moves is AABBBABBBB $\to$ AABBBABB $\to$ AABBBB $\to$ ABBB $\to$ AB $\to$ (empty string). So, the answer is $0$.

对于第一个测试用例，你无法进行任何操作，因此答案为 $3$。

对于第二个测试用例，一种最优的操作序列为 BABA $\to$ BA。因此，答案为 $2$。

对于第三个测试用例，一种最优的操作序列为 AABBBABBBB $\to$ AABBBABB $\to$ AABBBB $\to$ ABBB $\to$ AB $\to$（空字符串）。因此，答案为 $0$。