Смотритель зоопарка играет в игру. В этой игре он должен использовать бомбы, чтобы взрывать строку, состоящую из символов «A» и «B». Он может использовать бомбы, чтобы взорвать подстроку, которая равна либо «AB», либо «BB». Когда он взрывает такую подстроку, она удаляется из строки, а оставшиеся части строки объединяются вместе в новую строку.
Например, смотритель зоопарка может сделать следующие две операции: AABABBA \(\to\) AABBA \(\to\) AAA.
Смотритель зоопарка интересуется, какую наименьшую длину строки он может получить после нескольких взрывов. Можете ли вы ему помочь найти эту наименьшую длину строки?
Выходные данные
Для каждого набора входных данных выведите единственное целое число: наименьшую длину строки, которую смотритель зоопарка может получить.
Примечание
В первом наборе входных данных вы не можете сделать ни одну операцию, поэтому ответ \(3\).
Во втором наборе входных данных одна из оптимальных последовательностей операций BABA \(\to\) BA. Поэтому ответ \(2\).
В третьем наборе входных данных одна из оптимальных последовательностей операций AABBBABBBB \(\to\) AABBBABB \(\to\) AABBBB \(\to\) ABBB \(\to\) AB \(\to\) (пустая строка). Поэтому ответ \(0\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
AAA
BABA
AABBBABBBB
|
3
2
0
|