You are given a binary string S.
In one operation, you can pick an index i (1≤ i < |S|) and swap the characters S_{i} and S_{(i+1)}.

Find the minimum number of operations required, such that, the decimal representation of the final binary string is divisible by 3. If it is impossible to do so, print -1 instead.

------ Input Format ------

• The first line of input will contain a single integer T, denoting the number of test cases.
• Each test case consists of single line of input, containing a binary string S.

------ Output Format ------

For each test case, output on a new line, the minimum number of operations required, such that, the decimal representation of the final binary string is divisible by 3. If it is impossible to do so, print -1 instead.

------ Constraints ------

$1 ≤ T ≤ 10^{5}$
$1 ≤ |S| ≤ 3\cdot 10^{5}$
$S$ consists of $0$ and $1$ only.
- The sum of $|S|$ over all test cases won't exceed $3\cdot 10^{5}$.

----- Sample Input 1 ------
3
0000
111
11001
----- Sample Output 1 ------
0
-1
1
----- explanation 1 ------
Test case $1$: There is no need to apply any operation since the decimal representation of $0000$ is $0$ which is divisible by $3$.

Test case $2$: It can be shown that we cannot make the decimal representation of the string divisible by $3$ using any number of operations.

Test case $3$: The decimal representation of $11001$ is $25$ . Using one operation, we pick $i = 2$ and swap $S_{2}$ and $S_{3}$. Thus, the string becomes $10101$, whose decimal representation is $21$, which is divisible by $3$.

见题面

见题面