题目描述

给你一个由字符 $\texttt{A}$ 和 $\texttt{B}$ 组成的字符串 $s$。你一开始没有硬币。你可以进行两种操作：

• 选择一个子串 $^\dagger$ $\texttt{AB}$，将其变为 $\texttt{BC}$，并获得一个硬币。
• 选择一个子串 $^\dagger$ $\texttt{BA}$，将其变为 $\texttt{CB}$，并获得一个硬币。

你最多能获得多少个硬币？$^\dagger$ 长度为 $2$ 的子串指的是字符串中两个相邻的字符序列。

输入格式

输入包含多组测试用例。第一行为一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例的数量。

每个测试用例仅包含一行字符串 $s$（$1 \leq |s| \leq 2 \cdot 10^5$）。$s$ 的所有字符均为 $\texttt{A}$ 或 $\texttt{B}$。

所有测试用例中字符串 $s$ 的总长度不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一个整数，表示你最多能获得的硬币数量。

样例

8
ABBA
ABA
BAABA
ABB
AAAAAAB
BABA
B
AAA

2
1
3
1
6
2
0
0

样例说明

在第一个测试用例中，你可以进行如下操作获得 $2$ 个硬币：$\color{red}{\texttt{AB}}\texttt{BA} \to \texttt{BC}\color{red}{\texttt{BA}} \to \texttt{BCCB}$。

在第二个测试用例中，你可以进行如下操作获得 $1$ 个硬币：$\color{red}{\texttt{AB}}\texttt{A} \to \texttt{BCA}$。

在第三个测试用例中，你可以进行如下操作获得 $3$ 个硬币：$\color{red}{\texttt{BA}}\texttt{ABA} \to \texttt{CBA}\color{red}{\texttt{BA}} \to \texttt{C}\color{red}{\texttt{BA}}\texttt{CB} \to \texttt{CCBCB}$。

由 ChatGPT 4.1 翻译

来源

Codeforces 1873G，英文题名 ABBC or BACB。