ABBC 或 BACB

题目描述

给定一个由 A 和 B 组成的字符串 $s$。初始时，你没有金币。你可以执行以下两种操作：

• 选择一个子串 AB，将其变为 BC，并获得一枚金币。
• 选择一个子串 BA，将其变为 CB，并获得一枚金币。

你能获得的最大金币数量是多少？

输入格式

输入包含多个测试用例。第一行包含一个整数 $t$ ($1 \leq t \leq 1000$) —— 测试用例的数量。

每个测试用例只有一行，包含字符串 $s$ ($1 \leq |s| \leq 2 \cdot 10^5$)，其中 $s$ 由字符 A 或 B 构成。

所有测试用例的字符串长度之和不超过 $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}$