Make Even

题意翻译

Polycarp 有一个不包含数字 $0$ 的整数 $n$。他可以使用他的数字执行以下操作数次（可能为零）： 将 $n$ 的长度 $l\ (1 \leq l \leq |n|$，这里 $|n|$ 指 $n$ 的十进制长度 $)$ 的前缀反转，即反转 $n$ 的 前 $l$ 位数字。那么，第 $1$ 个数位（默认从左向右数，下文同理）将与第 $l$ 个数位交换，第 $2$ 个数位与第 $(l-1)$ 个交换......以此类推。 例如，如果 $n=123456789$ 且 $l=5$，则 $n$ 变换后的值将为 $543216789$。 对于不同的操作，$l$ 的值可能不同。 Polycarp 喜欢偶数，并且非常不耐烦。因此，他想用最少的操作次数使他的数字 $n$ 变成偶数。 **本题有多组数据。** ### 输入格式 第一行，一个整数 $t\ (1 \leq t \leq 10^4)$，表示数据的组数。 接下来 $t$ 行，每行一个数 $n\ (1 \leq n \leq 10^9)$。可以保证该数中各数位没有 $0$。 ### 输出格式 共 $t$ 行，每行一个整数，表示将该数字变成偶数的最小操作次数。如果无论如何操作，都无法变为偶数，则输出 `-1`。

题目描述

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.

输入输出样例

输入样例 #1

4
3876
387
4489
3

输出样例 #1

0
2
1
-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.