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 < 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.

见题面 Input 部分

见题面 Output 部分

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:

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