A14723 | Make Even

Polycarp has an integer $n$ that doesn't contain the digit 0. He can do the following operation with his number several (possibly zero) times:

- Reverse the prefix of length $l$ (in other words, $l$ leftmost digits) of $n$ . So, the leftmost digit is swapped with the $l$ -th digit from the left, the second digit from the left swapped with ( $l-1$ )-th left, etc. For example, if $n=123456789$ and $l=5$ , then the new value of $n$ will be $543216789$ .

Note that for different operations, the values of $l$ can be different. The number $l$ can be equal to the length of the number $n$ — in this case, the whole number $n$ is reversed.

Polycarp loves even numbers. Therefore, he wants to make his number even. At the same time, Polycarp is very impatient. He wants to do as few operations as possible.

Help Polycarp. Determine the minimum number of operations he needs to perform with the number $n$ to make it even or determine that this is impossible.

You need to answer $t$ independent test cases.

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

Each of the following $t$ lines contains one integer $n$ ( $1 \le n < 10^9$ ). It is guaranteed that the given number doesn't contain the digit 0.

Print $t$ lines. On each line print one integer — the answer to the corresponding test case. If it is impossible to make an even number, print -1.