CF1611A 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`。

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.