B. Ненависть к подпоследовальностям
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Shubham есть бинарная строка $$$s$$$. Бинарная строка  — это строка, содержащая только символы «0» и «1».

Он может выполнить следующую операцию над строкой любое количество раз:

  • Выбрать индекс строки, и поменять символ с этим индексом. Это означает, что если символ был «0», он становится «1», и наоборот.

Строка называется хорошей, если она не содержит строк «010» или «101» в качестве подпоследовательностей  — например, «1001» содержит «101» как подпоследовательность, следовательно, это не хорошая строка, а «1000» не содержит ни «010» ни «101» как подпоследовательностей, поэтому это хорошая строка.

Какое минимальное количество операций ему придется выполнить, чтобы строка стала хорошей? Можно показать, что с помощью данных операций можно сделать любую строку хорошей.

Строка $$$a$$$ является подпоследовательностью строки $$$b$$$, если $$$a$$$ может быть получена из $$$b$$$ удалением нескольких (возможно, ни одного или всех) символов.

Входные данные

В первой строке входных данных содержится одно целое число $$$t$$$ $$$(1\le t \le 100)$$$ — количество наборов входных данных.

Каждая из следующих $$$t$$$ строк содержит бинарную строку $$$s$$$ $$$(1 \le |s| \le 1000)$$$.

Выходные данные

Для каждой строки выведите минимальное количество операций необходимых для того, чтобы сделать ее хорошей.

Пример
Входные данные
7
001
100
101
010
0
1
001100
Выходные данные
0
0
1
1
0
0
2
Примечание

В наборах входных данных $$$1$$$, $$$2$$$, $$$5$$$, $$$6$$$ строки уже являются хорошими  — поэтому никаких операций не требуется.

Для набора $$$3$$$: «001» можно получить, поменяв первый символ, и это один из возможных способов получить хорошую строку.

Для набора $$$4$$$: «000» можно получить, поменяв второй символ, и это один из возможных способов получить хорошую строку.

Для набора $$$7$$$: «000000» можно получить, поменяв третий и четвертый символы, и это один из возможных способов получить хорошую строку.