C. Двоичная строка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана строка $$$s$$$, состоящая из символов 0 и/или 1.

Вы должны удалить несколько (возможно, ноль) символов из начала строки и несколько (возможно, ноль) символов с конца. Получившаяся строка может оказаться пустой. Стоимость удаления — это максимум из двух величин:

  • количество символов 0, оставшихся в строке;
  • количество символов 1, удаленных из строки.

Чему равна минимальная стоимость удаления, которую можно достигнуть?

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

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

Каждый набор входных данных состоит из единственной строки $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$), состоящей из символов 0 и/или 1.

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

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

Для каждого набора входных данных выведите одно целое число — минимальную возможную стоимость удаления.

Пример
Входные данные
5
101110110
1001001001001
0000111111
00000
1111
Выходные данные
1
3
0
0
0
Примечание

Рассмотрим наборы входных данных из примера:

  1. в первом наборе можно удалить два символа из начала и один символ с конца. Только один 1 был удален, только один 0 остался, поэтому стоимость равна $$$1$$$;
  2. во втором наборе можно удалить три символа из начала и шесть символов с конца. Два символа 0 останутся, будут удалены три символа 1, поэтому стоимость равна $$$3$$$;
  3. в третьем наборе входных данных оптимально удалить четыре символа из начала строки;
  4. в четвертом наборе входных данных оптимально удалить всю строку;
  5. в пятом наборе входных данных оптимально не удалять ни один символ.