D$.$ Binary String Sorting

time limit per test $2$ seconds

memory limit per test: $256$ megabytes

input: standard input

output: standard output

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

You can perform several operations on this string $($possibly zero$).$ There are two types of operations:

choose two consecutive elements and swap them. In order to perform this operation, you pay ${10}^{12}$ coins;

choose any element from the string and remove it$.$ In order to perform this operation, you pay ${10}^{12}+1$ coins.

Your task is to calculate the minimum number of coins required to sort the string $s$ in non$-$decreasing order $($i$.$ e$.$ transform $s$ so that

$s_1{s}_2$cdots$s_m,$ where $m$ is the length of the string after applying all operations$).$ An empty string is also considered sorted in non$-$

decreasing order.

Input

The first line contains a single integer $t(1t{10}^4)-$ the number of test cases.

The only line of each test case contains the string $s(1|s|3*{10}^5),$ consisting of only characters $0$ and$/$or $1.$

The sum of lengths of all given strings doesn't exceed $3*{10}^5.$

Output

For each test case, print a single integer $$ the minimum number of coins required to sort the string $s$ in non$-$decreasing order.

Example