Вам надається рядок \(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