A. Сделай чётное
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Поликарпа есть целое число $$$n$$$, которое не содержит цифр '0'. С этим числом он может делать следующую операцию несколько (возможно, ноль) раз:

  • Взять префикс длины $$$l$$$ (иными словами, левые $$$l$$$ цифр) числа $$$n$$$ и развернуть его. Так, самая левая цифра меняется местами с $$$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.

Пример
Входные данные
4
3876
387
4489
3
Выходные данные
0
2
1
-1
Примечание

В первом наборе входных данных $$$n=3876$$$, что уже является чётным числом. Поликарпу ничего не нужно делать, поэтому ответ $$$0$$$.

Во втором наборе входных данных $$$n=387$$$. Поликарпу необходимо сделать $$$2$$$ операции:

  1. Выбрать $$$l=2$$$ и развернуть префикс $$$\underline{38}7$$$. Число $$$n$$$ станет равным $$$837$$$. Это число нечётное.
  2. Выбрать $$$l=3$$$ и развернуть префикс $$$\underline{837}$$$. Число $$$n$$$ станет равным $$$738$$$. Это число чётное.

Можно показать, что $$$2$$$ — это минимально возможное количество операций, которое необходимо сделать Поликарпу для того, чтобы его число стало чётным.

В третьем наборе входных данных $$$n=4489$$$. Здесь Поликарп может развернуть всё число целиком (выбрать префикс длины $$$l=4$$$). Оно станет равным $$$9844$$$ и это чётное число.

В четвёртом тестовом примере $$$n=3$$$. Как бы Поликарп ни старался, но сделать чётное число у него не получится.