Polycarp 有一个不包含数字 0 的整数 $$$n$$$。他可以用他的数字执行以下操作多次(可能为零):
- 反转 $$$n$$$ 长度 $$$l$$$ 的前缀(换句话说,$$$l$$$ 最左边的数字)。因此,最左边的数字与左边第 $$$l$$$ 数字交换,左边第二个数字与左边第 ($$$l-1$$$) 交换,等等。例如,如果 $$$n=123456789$$$ 且 $$$l=5$$$,则 $$$n$$$ 的新值将为 $$$543216789$$$。
注意,对于不同的操作,$$$l$$$的值可以不同。数字 $$$l$$$ 可以等于数字 $$$n$$$ 的长度 - 在这种情况下,整个数字 $$$n$$$ 被反转。
坡旅甲喜欢偶数。所以,他想要让自己的数字变成偶数。与此同时,波利卡普也很不耐烦。他希望尽可能少做手术。
帮助波利卡普。确定他需要对数字 $$$n$$$ 执行的最少操作次数才能使其相等或确定这是不可能的。
您需要回答 $$$t$$$ 独立测试用例。
输入
第一行包含数字 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
以下 $$$t$$$ 行中的每一行都包含一个整数 $$$n$$$ ($$$1 \le n < 10^9$$$)。保证给定的数字不包含数字0。
输出
打印 $$$t$$$ 行。在每一行打印一个整数——相应测试用例的答案。如果无法生成偶数,则打印 -1。
示例
输入 #1
4 3876 387 4489 3
输出 #1
0 2 1 -1
注意
在第一个测试用例中,$$$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$$$。无论波利卡普如何努力,他都无法得到偶数。