题目描述

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。

样例

4
3876
387
4489
3

0
2
1
-1