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

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

Вы можете выполнить несколько (возможно, ноль) операций над строкой. Каждая операция имеет один из двух типов:

  • выбрать два соседних элемента строки и поменять их местами. Такой вид операции стоит $$$10^{12}$$$ монет;
  • выбрать любой элемент строки и удалить его. Такой вид операции стоит $$$10^{12}+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$$$ в порядке неубывания.

Пример
Входные данные
6
100
0
0101
00101101
1001101
11111
Выходные данные
1000000000001
0
1000000000000
2000000000001
2000000000002
0
Примечание

В первом примере необходимо удалить $$$1$$$-й элемент, чтобы строка стала равной 00.

Во втором примере строка уже отсортирована.

В третьем примере необходимо поменять местами $$$2$$$-й и $$$3$$$-й элементы, чтобы строка стала равной 0011.

В четвертом примере необходимо поменять местами $$$3$$$-й и $$$4$$$-й элементы, чтобы строка стала равной 00011101, а затем удалить $$$7$$$-й элемент, чтобы строка стала равной 0001111.

В пятом примере необходимо удалить $$$1$$$-й элемент, чтобы строка стала равной 001101, а затем удалить $$$5$$$-й элемент, чтобы строка стала равной 00111.

В шестом примере строка уже отсортирована.