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

Задана строка $$$s$$$, состоящая только из символов '0' и '1'.

Требуется выбрать последовательную подстроку $$$s$$$ и удалить все вхождения символа, который является строгим меньшинством в ней, из подстроки.

То есть, если количество '0' в подстроке строго меньше количества '1', то удалить все вхождения '0' из подстроки. Если количество '1' строго меньше количества '0', то удалить все вхождения '1'. Если количества совпадают, то не делать ничего.

Необходимо применить операцию ровно один раз. Какое наибольшее количество символов можно удалить?

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

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

В единственной строке каждого набора входных данных содержится непустая строка $$$s$$$, состоящая только из символов '0' и '1'. Длина $$$s$$$ не превосходит $$$2 \cdot 10^5$$$.

Суммарная длина строк $$$s$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

На каждый набор входных данных выведите одно целое число — наибольшее количество символов, которые можно удалить, если применить операции ровно один раз.

Пример
Входные данные
4
01
1010101010111
00110001000
1
Выходные данные
0
5
3
0
Примечание

В первом наборе входных данных можно выбрать подстроки «0», «1» или «01». В «0» количество '0' равно $$$1$$$, количество '1' равно $$$0$$$. '1' — строгое меньшинство, поэтому все его вхождения удаляются из подстроки. Однако, раз там их $$$0$$$, то ничего не меняется. То же для «1». А в «01» ни '0', ни '1', не являются строгим меньшинством. Поэтому ничего не меняется. Так что не существует способа удалить какие-либо символы.

Во втором наборе входных данных можно выбрать подстроку «10101010101». Она содержит $$$5$$$ символов '0' и $$$6$$$ символов '1'. '0' является строгим меньшинством. Поэтому можно удалить все его вхождения. Существуют и другие подстроки, которые дают тот же ответ.

В третьем наборе входных данных можно выбрать подстроку «011000100». Она содержит $$$6$$$ символов '0' и $$$3$$$ символа '1'. '1' является строгим меньшинством. Поэтому можно удалить все его вхождения.