Вам дана бинарная строка\(^{\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\).
Для каждого набора входных данных выведите одно целое число — минимальное количество частей, необходимое для того, чтобы можно было переставить строку в отсортированную бинарную строку.
Первый пример изображен в условии. Можно доказать, что вам понадобится не менее \(3\) частей.
Во втором и третьем примерах случаях бинарная строка уже отсортирована, поэтому нужна только \(1\) часть.
В четвертом примере вам нужно сделать один разрез между двумя символами и переставить их, чтобы получить строку \(\texttt{01}\).
6 11010 00000000 1 10 0001111 0110
3 1 1 2 1 2
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач