Description

“41，43，47，51....尝试去数质数吧，质数是任谁也没法分割的孤独的数字”，对于普奇神父的名言，Cc表示放tnn的屁！Cc自小开始就很讨厌质数，相反，他很喜欢合数，尤其是偶数，所以Cc立志创造一个只有偶数的世界！在历尽艰难险阻后，Cc终于成功获得了替身能力！其替身名是 [Prime Star · The World] ，替身能力为：将任意一个不含0的正整数经过x操作后修改为一个偶数。操作如下：

对于一个不含有数字0的正整数n，可以将其最左边的连续l个数字颠倒顺序，得到一个新的数字，且这个值将为n的新值。例如：如果n = 123456789 和 l = 5，则n的新值将为543216789。

现在Cc想知道对于一个不含有0的正整数，要将这个数字变为一个偶数，最少需要多少次操作(操作数可以是0)。

Input Format

首先第一行会输入一正整数t(1≤t≤100000)，表示接下来共有t组测试样例。

第 2 到t + 1行，每行会输入一个不含有数字0的正整数n(1≤n≤1000000000)。

题目中的l为任意符合题意的值，由你自己来选取。

Output Format

对于每行输入，输出一行，其中包含一个非负整数，表示要将这个正整数变为一个偶数所需的最少的操作次数。如果这个数字无论进行多少次操作都没法变成一个偶数，那么请输出“-1”(不带引号)。

4
3876
387
4489
3

0
2
1
-1

Hint

对于第二个测试样例：387，我们总共要进行两次操作：

1.首先选取l = 2，使其前两位数字交换，即原数字变为：837，这个数字是个奇数。

2.然后再选取l = 3，使其前三位数字交换，即原数字变为：738，这个数字是一个偶数。

Source

1816 Online Judge 10.100.0.232