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

Давайте определим циклический сдвиг некоторой строки $$$s$$$ как преобразование из $$$s_1 s_2 \dots s_{n-1} s_{n}$$$ в $$$s_{n} s_1 s_2 \dots s_{n-1}$$$. Другими словами, вы берете один последний символ $$$s_n$$$ и помещаете его перед первым символом, сдвигая все остальные символы вправо.

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

За одну операцию вы можете выбрать любую подстроку $$$s_l s_{l+1} \dots s_r$$$ ($$$1 \le l < r \le |s|$$$) и выполнить ее циклический сдвиг. Стоимость такой операции равна $$$r - l + 1$$$ (или же длине выбранной подстроки).

Вы можете выполнять данную операцию любое количество раз. Какова минимальная суммарная стоимость, чтобы отсортировать строку $$$s$$$ в порядке неубывания?

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

В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

В первой и единственной строке каждого набора задана бинарная строка $$$s$$$ ($$$2 \le |s| \le 2 \cdot 10^5$$$; $$$s_i \in$$$ {0, 1}) — строка, которую нужно отсортировать.

Дополнительное ограничение на входные данные: сумма длин строк по всем наборам не превышает $$$2 \cdot 10^5$$$.

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

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

Пример
Входные данные
5
10
0000
11000
101011
01101001
Выходные данные
2
0
9
5
11
Примечание

В первом наборе входных данных вы можете выбрать всю строку и выполнить циклический сдвиг: 10 $$$\rightarrow$$$ 01. Длина подстроки равна $$$2$$$, поэтому стоимость составляет $$$2$$$.

Во втором наборе строка уже отсортирована, поэтому вам не нужно выполнять никаких операций.

В третьем наборе одной из оптимальных стратегий является следующая:

  1. выбрать подстроку $$$[1, 3]$$$: 11000 $$$\rightarrow$$$ 01100;
  2. выбрать подстроку $$$[2, 4]$$$: 01100 $$$\rightarrow$$$ 00110;
  3. выбрать подстроку $$$[3, 5]$$$: 00110 $$$\rightarrow$$$ 00011.
Общая стоимость равна $$$3 + 3 + 3 = 9$$$.