Дана строка \(s\), состоящая из символов \(\texttt{A}\) и \(\texttt{B}\). Изначально у вас нет монет. Вы можете выполнять два типа операций:
\(^\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\).
Для каждого набора входных данных выведите одно целое число — максимальное количество монет, которое вы можете получить.
В первом примере вы можете выполнить следующие операции, чтобы получить \(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}\(\)
8 ABBA ABA BAABA ABB AAAAAAB BABA B AAA
2 1 3 1 6 2 0 0
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач