题目描述

动物管理员正在玩一个游戏。在这个游戏中，动物管理员需要用炸弹炸掉一个只包含字母 'A' 和 'B' 的字符串。他可以用炸弹炸掉一个子串，这个子串要么是 "AB"，要么是 "BB"。当他炸掉这样的一个子串后，这个子串会从字符串中删除，剩下的部分会拼接在一起。

例如，动物管理员可以进行两次这样的操作：AABABBA $\to$ AABBA $\to$ AAA。

动物管理员想知道，他能得到的最短字符串长度是多少。你能帮他找到最短字符串的长度吗？

输入格式

每个测试点包含多个测试用例。第一行包含一个整数 $t$ $(1 \leq t \leq 20000)$ —— 测试用例的数量。接下来的 $t$ 行，每行包含一个非空字符串 $s$：动物管理员需要炸掉的字符串。保证 $s$ 中所有字符都是 'A' 或 'B'。

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

输出格式

对于每个测试用例，输出一个整数：动物管理员能得到的最短字符串的长度。

说明/提示

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

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

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

由 ChatGPT 4.1 翻译

样例

3
AAA
BABA
AABBBABBBB

3
2
0