## Make Even solution codechef

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 (𝑙−1l−1)-th left, etc. For example, if 𝑛=123456789n=123456789 and 𝑙=5l=5, then the new value of 𝑛n will be 543216789543216789.

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.

Also read: ATM and Students solution codeforces

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≤𝑡≤1041≤t≤104) — the number of test cases.

Each of the following 𝑡t lines contains one integer 𝑛n (1≤𝑛<1091≤n<109). 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.

input

4 3876 387 4489 3

output Make Even solution codechef

0 2 1 -1

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

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

- Select 𝑙=2l=2 and reverse the prefix 38⎯⎯⎯⎯738_7. The number 𝑛n becomes 837837. This number is odd.
- Select 𝑙=3l=3 and reverse the prefix 837⎯⎯⎯⎯⎯⎯837_. The number 𝑛n becomes 738738. This number is even.

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

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

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