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

Вам задана бинарная строка $$$s$$$ (строка, состоящая только из символов 0 и/или 1).

Вы можете выполнять операции двух типов над $$$s$$$:

  1. удалить один символ из $$$s$$$. Эта операция стоит $$$1$$$ монету;
  2. поменять местами любую пару символов в $$$s$$$. Эта операция бесплатна (стоит $$$0$$$ монет).

Вы можете выполнять эти операции в любом порядке любое количество раз.

Давайте обозначим строку, которую вы получили после выполнения вышеуказанных операций, как $$$t$$$. Строка $$$t$$$ является хорошей, если для каждого $$$i$$$ от $$$1$$$ до $$$|t|$$$ $$$t_i \neq s_i$$$ ($$$|t|$$$ — длина строки $$$t$$$). Пустая строка — всегда хорошая. Обратите внимание, что вы сравниваете результирующую строку $$$t$$$ с исходной строкой $$$s$$$.

Какова минимальная суммарная стоимость сделать строку $$$t$$$ хорошей?

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следуют $$$t$$$ наборов входных данных.

В единственной строке каждого набора задана бинарная строка $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$; $$$s_i \in \{$$$0, 1$$$\}$$$) — исходная строка, состоящая из символов 0 и/или 1.

Дополнительное ограничение на входные данные: общая длина всех строк $$$s$$$ не превышает $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите минимальную суммарную стоимость сделать строку $$$t$$$ хорошей.

Пример
Входные данные
4
0
011
0101110001
111100
Выходные данные
1
1
0
4
Примечание

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

Во втором тесте вы, например, можете удалить второй символ из $$$s$$$, чтобы получить строку 01, а затем поменять местами первый и второй символы, чтобы получить строку $$$t$$$ $$$=$$$ 10. Строка $$$t$$$ — хорошая, так как $$$t_1 \neq s_1$$$ и $$$t_2 \neq s_2$$$. Общая стоимость составляет $$$1$$$.

В третьем тесте вы, например, можете поменять местами $$$s_1$$$ с $$$s_2$$$, $$$s_3$$$ с $$$s_4$$$, $$$s_5$$$ с $$$s_7$$$, $$$s_6$$$ с $$$s_8$$$ и $$$s_9$$$ с $$$s_{10}$$$. Вы получите строку $$$t$$$ $$$=$$$ 1010001110. Все операции обмена бесплатны, поэтому общая стоимость составляет $$$0$$$.