AT_arc224_e.ABC|AB|A

You are given a string $S$ consisting of A, B, and C.

You can perform the following operation zero or more times.

• Choose a substring (contiguous subsequence) of $S$ that is A, AB, or ABC, and delete it. The remaining characters are concatenated, preserving their order.

Find the minimum possible length of $S$ in the end.

$T$ test cases are given; solve each of them.

给你一个仅由字符 A、B 和 C 组成的字符串 $S$。

你可以执行以下操作零次或多次：

• 选择 $S$ 的一个子串（连续子序列），该子串为 A、AB 或 ABC，并将其删除。剩余字符按原顺序拼接。

求最终 $S$ 的最小可能长度。

共给出 $T$ 组测试数据，请对每组数据求解。

The input is given from Standard Input in the following format, where $\mathrm{case}_i$ denotes the $i$-th test case:

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

Each test case is given in the following format:

$S$

输入从标准输入给出，格式如下，其中 $\mathrm{case}_i$ 表示第 $i$ 个测试用例：

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

每个测试用例的格式如下：

$S$

Output $T$ lines. The $i$-th line should contain the answer for the $i$-th test case.

输出 $T$ 行。第 $i$ 行应包含第 $i$ 个测试用例的答案。

Sample 1 Explanation:
This input contains five test cases.

For the first test case, we can perform the operations as follows, for example.

• Choose and delete the third through fifth characters of $S=$ CAABCB. After the operation, $S$ becomes CAB.
• Choose and delete the second through third characters of $S=$ CAB. After the operation, $S$ becomes C.
• No further operations can be performed. $S=$ C has length $1$, which is the minimum achievable.

Constraints

• $T$ is an integer between $1$ and $10^5$, inclusive.
• $S$ is a string consisting of A, B, and C with length between $1$ and $10^6$, inclusive.
• The sum of $|S|$ in each input is at most $10^6$.

样例 1 解释：
该输入包含五个测试用例。

对于第一个测试用例，我们可以按如下方式执行操作（例如）：

• 选择并删除 $S=$ CAABCB 的第 3 至第 5 个字符。操作后，$S$ 变为 CAB。
• 选择并删除 $S=$ CAB 的第 2 至第 3 个字符。操作后，$S$ 变为 C。
• 无法再执行任何操作。此时 $S=$ C 的长度为 $1$，即所能达到的最小长度。

约束条件

• $T$ 是一个介于 $1$ 到 $10^5$（含）之间的整数。
• $S$ 是一个仅由字符 A、B 和 C 组成的字符串，其长度介于 $1$ 到 $10^6$（含）之间。
• 所有输入中 $|S|$ 的总和不超过 $10^6$。