题目描述

给定一个只包含 A 和 B 的字符串 $S$。

你可以对该字符串重复进行如下操作：

• 从 $S$ 中选择连续的 $3$ 个字符，这 $3$ 个字符等于 AAB 或 BAA，然后将这 $3$ 个字符从 $S$ 中删除（删除后剩余的字符会连接在一起）。

请你求出最多可以进行多少次这样的操作。

给定 $T$ 个测试用例，请分别输出每个测试用例的答案。

输入格式

输入以如下格式从标准输入读入。

$T$
$\text{case}_1$
$\vdots$
$\text{case}_T$

每个测试用例输入一行，包含一个只由 A 和 B 组成的字符串 $S$。

输出格式

请输出 $T$ 行，第 $i$ 行输出第 $i$ 个测试用例最多可以进行的操作次数。

样例 1

输入

10
AABAAAB
BAAAAABBA
A
B
ABA
BAA
AAAAAA
AAAABB
AABABBAABBABAAAABBAA
BBAAAAABAAAAABABAABA

输出

2
3
0
0
0
1
0
2
5
6

说明/提示

限制

• $1\leq T\leq 10^5$
• $S$ 只包含 A 和 B 字符。
• $1\leq |S|\leq 10^6$
• 所有测试用例的 $|S|$ 之和不超过 $10^6$。

样例解释 1

对于第 $1$、$2$ 个测试用例，最大化操作次数的一种方法如下：

• AABAAAB → AAAB → A
• BAAAAABBA → BAAABA → BAA → （空字符串）

由 ChatGPT 4.1 翻译