Давайте определим циклический сдвиг некоторой строки $$$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$$$.
Для каждого набора входных данных выведите одно целое число — минимальную суммарную стоимость, чтобы сделать строку отсортированной, используя вышеуказанную операцию произвольное количество раз.
51000001100010101101101001
2 0 9 5 11
В первом наборе входных данных вы можете выбрать всю строку и выполнить циклический сдвиг: 10 $$$\rightarrow$$$ 01. Длина подстроки равна $$$2$$$, поэтому стоимость составляет $$$2$$$.
Во втором наборе строка уже отсортирована, поэтому вам не нужно выполнять никаких операций.
В третьем наборе одной из оптимальных стратегий является следующая:
