给定一个字符串 $$$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}$$$$$$