Вам надається рядок ~S~, що мiстить символи ~A~ та ~B~. Ваше завдання - перетворити його таким чином, щоб не було однакових сумiжних символiв. Для цього вам дозволяється видалити нуль або бiльше символiв у рядку.

Ваше завдання - знайти мiнiмальну кiлькiсть необхiдних видалень.

Формат вхiдних даних

Перший рядок мiстить ~T~ ~(1 \le T \le 10)~ - кiлькiсть тестiв.

Далi iдуть рядки з тестами. Кожен рядок - один тест, що мiстить ~S~ ~(1 \le S \le 10^5 )~

Формат вихiдних даних

Для кожного тесту в окремому рядку вивести мiнiмальну кiлькiсть видалень

Приклад вхідних даних

5
AAAA
BBBBB
ABABABAB
BABABA
AAABBB

Приклад вихідних даних

3
4
0
0
4