← 返回题目列表

Codeforces · 1873/G

G. ABBC 或 BACB

中文机器翻译题面 查看原题

给定一个字符串 $$$s$$$,由字符 $$$\texttt{A}$$$ 和 $$$\texttt{B}$$$ 组成。最初你没有硬币。您可以执行两种类型的操作:

- 选择一个子字符串$$$^\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$$$。

输出

对于每个测试用例,输出一个整数 - 您可以获得的最大硬币数量。

示例

输入 #1

8
ABBA
ABA
BAABA
ABB
AAAAAAB
BABA
B
AAA

输出 #1

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}$$$$$$