Вам дана двоичная строка $$$s$$$, состоящая только из символов 0 и/или 1.
Вы можете выполнить несколько (возможно, ноль) операций над строкой. Каждая операция имеет один из двух типов:
Ваша задача — определить минимальное количество монет, необходимое для сортировки строки $$$s$$$ в порядке неубывания (т. е. преобразовать $$$s$$$ таким образом, что $$$s_1 \le s_2 \le \dots \le s_m$$$, где $$$m$$$ — длина строки после применения всех операций). Пустая строка также считается отсортированной в порядке неубывания.
Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.
Единственная строка каждого набора содержит строку $$$s$$$ ($$$1 \le |s| \le 3 \cdot 10^5$$$), состоящую только из символов 0 и/или 1.
Сумма длин всех заданных строк не превосходит $$$3 \cdot 10^5$$$.
Для каждого набора входных данных выведите одно целое число — минимальное количество монет, необходимое для сортировки строки $$$s$$$ в порядке неубывания.
61000010100101101100110111111
1000000000001 0 1000000000000 2000000000001 2000000000002 0
В первом примере необходимо удалить $$$1$$$-й элемент, чтобы строка стала равной 00.
Во втором примере строка уже отсортирована.
В третьем примере необходимо поменять местами $$$2$$$-й и $$$3$$$-й элементы, чтобы строка стала равной 0011.
В четвертом примере необходимо поменять местами $$$3$$$-й и $$$4$$$-й элементы, чтобы строка стала равной 00011101, а затем удалить $$$7$$$-й элемент, чтобы строка стала равной 0001111.
В пятом примере необходимо удалить $$$1$$$-й элемент, чтобы строка стала равной 001101, а затем удалить $$$5$$$-й элемент, чтобы строка стала равной 00111.
В шестом примере строка уже отсортирована.
