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

Polycarp 有一个不含数字 0 的整数 $n$。他可以对这个数执行以下操作若干次（也可以不执行）：

• 将 $n$ 的长度为 $l$ 的前缀（即最左边的 $l$ 位数字）进行翻转。换言之，最左边的数字与从左起第 $l$ 位数字交换，从左起第二位数字与从左起第 $l-1$ 位数字交换，依此类推。例如，若 $n=123456789$ 且 $l=5$，则 $n$ 的新值为 $543216789$。

注意：不同操作中所选的 $l$ 值可以不同。$l$ 可以等于 $n$ 的位数——此时整个数 $n$ 被完全翻转。

Polycarp 喜欢偶数，因此他希望使自己的数变为偶数。同时，Polycarp 非常没有耐心，他希望操作次数尽可能少。

请帮助 Polycarp：确定使 $n$ 变为偶数所需的最少操作次数；若不可能实现，则说明这一点。

你需要回答 $t$ 个相互独立的测试用例。

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 \lt 10^9$). It is guaranteed that the given number doesn't contain the digit 0.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 表示测试用例的数量。

接下来的 $t$ 行，每行包含一个整数 $n$（$1 \le n \lt 10^9$）。保证给定的数不包含数字 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.

输出 $t$ 行。每行输出一个整数——对应测试用例的答案。如果无法得到偶数，则输出 $-1$。

In the first test case, $n=3876$, which is already an even number. Polycarp doesn't need to do anything, so the answer is $0$.

In the second test case, $n=387$. Polycarp needs to do $2$ operations:

1. Select $l=2$ and reverse the prefix $\underline{38}7$. The number $n$ becomes $837$. This number is odd.
2. Select $l=3$ and reverse the prefix $\underline{837}$. The number $n$ becomes $738$. This number is even.

It can be shown that $2$ is the minimum possible number of operations that Polycarp needs to do with his number to make it even.

In the third test case, $n=4489$. Polycarp can reverse the whole number (choose a prefix of length $l=4$). It will become $9844$ and this is an even number.

In the fourth test case, $n=3$. No matter how hard Polycarp tried, he would not be able to make an even number.

在第一个测试用例中，$n=3876$，它本身已是偶数。Polycarp 无需进行任何操作，因此答案为 $0$。

在第二个测试用例中，$n=387$。Polycarp 需要执行 $2$ 次操作：

1. 选择 $l=2$，翻转前缀 $\underline{38}7$。此时数字 $n$ 变为 $837$。该数为奇数。
2. 选择 $l=3$，翻转前缀 $\underline{837}$。此时数字 $n$ 变为 $738$。该数为偶数。

可以证明，$2$ 是 Polycarp 为使该数字变为偶数所需执行的最少操作次数。

在第三个测试用例中，$n=4489$。Polycarp 可以翻转整个数字（即选择长度为 $l=4$ 的前缀）。结果变为 $9844$，这是一个偶数。

在第四个测试用例中，$n=3$。无论 Polycarp 如何尝试，他都无法得到一个偶数。