ABC|AB|A

时间限制：2s
空间限制：1024MB

题目描述

给定一个仅由字符 A、B、C 组成的字符串 $S$。你可以进行任意多次如下操作：

• 从 $S$ 中选择一个恰为 A、AB 或 ABC 的子串并将其删除，剩余字符保持相对顺序并重新拼接。

求最终字符串长度的最小可能值。共有 $T$ 组测试数据。

输入格式

T
S_1
S_2
\vdots
S_T

输出格式

输出 $T$ 行，第 $i$ 行输出第 $i$ 组测试数据的答案。

样例输入 1

5
CAABCB
B
AAABBC
AABBCC
CABCCBCBAABCBBBAABAABACABBC

样例输出 1

1
1
0
1
7

数据范围

$1\le T\le 10^5$；每个 $S$ 的长度在 $1$ 到 $10^6$ 之间；同一输入内所有字符串长度之和不超过 $10^6$。