D. Бинарное разбиение
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана бинарная строка$$$^{\dagger}$$$. Пожалуйста, найдите минимальное количество частей, которые вам нужно отрезать, чтобы полученные части можно было переставить в отсортированную бинарную строку.

Обратите внимание, что:

  • каждый символ должен принадлежать ровно одной из частей;
  • части должны быть непрерывными подстроками исходной строки;
  • вам нужно использовать все части при перестановке.

$$$^{\dagger}$$$ Бинарная строка — это строка, состоящая из символов $$$\texttt{0}$$$ и $$$\texttt{1}$$$. Отсортированная бинарная строка — это бинарная строка, в которой все символы $$$\texttt{0}$$$ идут перед всеми символами $$$\texttt{1}$$$.

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

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

Единственная строка каждого набора содержит одну строку $$$s$$$ ($$$1 \leq |s| \leq 500$$$), состоящую из символов $$$\texttt{0}$$$ и $$$\texttt{1}$$$, где $$$|s|$$$ обозначает длину строки $$$s$$$.

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

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

Пример
Входные данные
6
11010
00000000
1
10
0001111
0110
Выходные данные
3
1
1
2
1
2
Примечание

Первый пример изображен в условии. Можно доказать, что вам понадобится не менее $$$3$$$ частей.

Во втором и третьем примерах случаях бинарная строка уже отсортирована, поэтому нужна только $$$1$$$ часть.

В четвертом примере вам нужно сделать один разрез между двумя символами и переставить их, чтобы получить строку $$$\texttt{01}$$$.