G. ABBC или BACB
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана строка $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — максимальное количество монет, которое вы можете получить.

Пример
Входные данные
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}$$$$$$