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