Let's define a cyclic shift of some string $$$s$$$ as a transformation from $$$s_1 s_2 \dots s_{n-1} s_{n}$$$ into $$$s_{n} s_1 s_2 \dots s_{n-1}$$$. In other words, you take one last character $$$s_n$$$ and place it before the first character while moving all other characters to the right.

You are given a binary string $$$s$$$ (a string consisting of only 0-s and/or 1-s).

In one operation, you can choose any substring $$$s_l s_{l+1} \dots s_r$$$ ($$$1 \le l \lt r \le |s|$$$) and cyclically shift it. The cost of such operation is equal to $$$r - l + 1$$$ (or the length of the chosen substring).

You can perform the given operation any number of times. What is the minimum total cost to make $$$s$$$ sorted in non-descending order?

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first and only line of each test case contains a binary string $$$s$$$ ($$$2 \le |s| \le 2 \cdot 10^5$$$; $$$s_i \in$$$ {0, 1}) — the string you need to sort.

Additional constraint on the input: the sum of lengths of strings over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print the single integer — the minimum total cost to make string sorted using operation above any number of times.

Note

In the first test case, you can choose the whole string and perform a cyclic shift: 10 $$$\rightarrow$$$ 01. The length of the substring is $$$2$$$, so the cost is $$$2$$$.

In the second test case, the string is already sorted, so you don't need to perform any operations.

In the third test case, one of the optimal strategies is the next:

choose substring $$$[1, 3]$$$: 11000 $$$\rightarrow$$$ 01100;
choose substring $$$[2, 4]$$$: 01100 $$$\rightarrow$$$ 00110;
choose substring $$$[3, 5]$$$: 00110 $$$\rightarrow$$$ 00011.

The total cost is $$$3 + 3 + 3 = 9$$$.

Idx	Name	Rating
A	Two Friends	800
B	Shifts and Sorting	1000
C	Minimizing the Sum	1700
D	Shop Game	1900
E	Unique Array	2400
F	Card Pairing	3000

Educational Codeforces Round 165 (Rated for Div. 2)