A. Строка
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана строка $$$s$$$ длины $$$n$$$, состоящая из символов $$$\mathtt{0}$$$ и $$$\mathtt{1}$$$. За одну операцию вы можете выбрать непустую подпоследовательность $$$t$$$ из $$$s$$$, такую, что любые два соседних символа $$$t$$$ различны. Затем вы инвертируете каждый символ в $$$t$$$ ($$$\mathtt{0}$$$ становится $$$\mathtt{1}$$$, а $$$\mathtt{1}$$$ становится $$$\mathtt{0}$$$). Например, если $$$s=\mathtt{\underline{0}0\underline{101}}$$$ и $$$t=s_1s_3s_4s_5=\mathtt{0101}$$$, то после операции $$$s$$$ станет $$$\mathtt{\underline{1}0\underline{010}}$$$.

Вычислите минимальное количество операций, необходимых для того, чтобы сделать все символы $$$s$$$ равными $$$\mathtt{0}$$$.

Напомним, что для строки $$$s = s_1s_2\ldots s_n$$$, любая строка $$$t=s_{i_1}s_{i_2}\ldots s_{i_k}$$$ ($$$k\ge 1$$$), где $$$1\leq i_1 < i_2 < \ldots <i_k\leq n$$$, является подпоследовательностью $$$s$$$.

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

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

Единственная строка каждого набора входных данных содержит строку $$$s$$$ ($$$1\le |s|\le 50$$$), где $$$|s|$$$ обозначает длину строки $$$s$$$.

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

Для каждого набора входных данных выведите минимальное количество операций, необходимых для изменения всех символов в $$$s$$$ на $$$\mathtt{0}$$$.

Пример
Входные данные
5
1
000
1001
10101
01100101011101
Выходные данные
1
0
2
3
8
Примечание

В первом наборе входных данных вы можете инвертировать $$$s_1$$$. Строка $$$s$$$ станет $$$\mathtt{0}$$$, поэтому ответ равен $$$1$$$.

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

  1. Инвертируйте $$$s_1s_2s_3s_4s_5$$$. Тогда $$$s$$$ станет $$$\mathtt{\underline{01010}}$$$.
  2. Инвертируйте $$$s_2s_3s_4$$$. Тогда $$$s$$$ станет $$$\mathtt{0\underline{010}0}$$$.
  3. Инвертируйте $$$s_3$$$. Тогда $$$s$$$ станет $$$\mathtt{00\underline{0}00}$$$.

Можно показать, что вы не можете изменить все символы в $$$s$$$ на $$$\mathtt{0}$$$ менее чем за три операции, поэтому ответ равен $$$3$$$.