Polycarp has an integer $n$ that doesn't contain the digit 0. He can do the following operation with his number several (possibly zero) times:

Reverse the prefix of length $l$ (in other words, $l$ leftmost digits) of $n$. So, the leftmost digit is swapped with the $l$-th digit from the left, the second digit from the left swapped with ($l-1$)-th left, etc. For example, if $n=123456789$ and $l=5$, then the new value of $n$ will be $543216789$.

Note that for different operations, the values of $l$ can be different. The number $l$ can be equal to the length of the number $n$ — in this case, the whole number $n$ is reversed.

Polycarp loves even numbers. Therefore, he wants to make his number even. At the same time, Polycarp is very impatient. He wants to do as few operations as possible.

Help Polycarp. Determine the minimum number of operations he needs to perform with the number $n$ to make it even or determine that this is impossible.

You need to answer $t$ independent test cases.


-----Input-----

The first line contains the number $t$ ($1 \le t \le 10^4$) — the number of test cases.

Each of the following $t$ lines contains one integer $n$ ($1 \le n < 10^9$). It is guaranteed that the given number doesn't contain the digit 0.


-----Output-----

Print $t$ lines. On each line print one integer — the answer to the corresponding test case. If it is impossible to make an even number, print -1.


-----Examples-----

Input
4
3876
387
4489
3
Output
0
2
1
-1


-----Note-----

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:

Select $l=2$ and reverse the prefix $\underline{38}7$. The number $n$ becomes $837$. This number is odd.

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.

Difficulty: EASY
Tags: Mathematics

Constructive algorithms

Starter code:

Solutions:
import sys

def solve(n, string):
	if int(string[n - 1]) % 2 == 0:
		print(0)
		return
	elif int(string[0]) % 2 == 0:
		print(1)
		return
	else:
		for i in range(1, n - 1):
			if int(string[i]) % 2 == 0:
				print(2)
				return
		print(-1)
		return

def main():
	test_case = int(sys.stdin.readline())
	for tc in range(test_case):
		string = sys.stdin.readline().strip('\n')
		n = len(string)
		solve(n, string)
main()


from sys import stdin
test = int(stdin.readline())
for t in range(test):
	nums = int(stdin.readline())
	if nums % 2 == 0:
		print(0)
	elif int(str(nums)[0]) % 2 == 0:
		print(1)
	else:
		check = True
		for i in str(nums):
			if int(i) % 2 == 0:
				check = False
		if check:
			print(-1)
		else:
			print(2)


import sys
import math
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def inltstr():
	return list(map(str, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def factorial(n):
	if n == 1:
		return n
	elif n < 1:
		return 'NA'
	else:
		return n * factorial(n - 1)

def coeffBin(k):
	return factorial(k + 1) / (factorial(2) * factorial(k - 1))

def solve(num):
	num = num.strip('\n')
	if int(num) % 2 == 0:
		return '0'
	elif int(num[0]) % 2 == 0:
		return '1'
	else:
		for c in num:
			if int(c) % 2 == 0:
				return '2'
	return '-1'
res = []
iter = inp()
i = 0
while i < iter:
	arr = input()
	result = solve(arr)
	res.append(result)
	i += 1
for r in res:
	print(r)


import sys

def b(l, n, f):
	a = 0
	x = n - 1
	while a <= x:
		m = a + (x - a) // 2
		if l[m] == f:
			return m
		elif l[m] > f:
			x = m - 1
		else:
			a = m + 1
	return None
for i in range(int(sys.stdin.readline())):
	n = sys.stdin.readline()
	if int(n) % 2 == 0:
		print(0)
	elif int(n[0]) % 2 == 0:
		print(1)
	else:
		c = 0
		for i in range(1, len(n) - 1):
			if int(n[i]) % 2 == 0:
				c = 1
				break
		if c == 1:
			print(2)
		else:
			print(-1)


t = int(input())
nums = [None] * t
ans = [False] * t
for i in range(t):
	nums[i] = input()
	if '2' not in nums[i] and '4' not in nums[i] and ('6' not in nums[i]) and ('8' not in nums[i]):
		ans[i] = -1
	elif int(nums[i]) % 2 == 0:
		ans[i] = 0
	elif int(nums[i][0]) % 2 == 0:
		ans[i] = 1
	else:
		ans[i] = 2
for i in ans:
	print(i)


import sys
t = int(sys.stdin.readline())
for i in range(t):
	n = int(sys.stdin.readline())
	s = str(n)
	if n < 0 and n % 2 != 0:
		print(-1)
	elif n % 2 == 0:
		print(0)
	elif int(s[0]) % 2 == 0:
		print(1)
	else:
		even = False
		for i in s:
			if int(i) % 2 == 0:
				even = True
				break
		if even == True:
			print(2)
		else:
			print(-1)


import sys
lst = ['0', '2', '4', '6', '8']
for _ in range(int(sys.stdin.readline().strip())):
	ans = -1
	s = sys.stdin.readline().strip()
	if s[-1] in lst:
		ans = 0
	elif s[0] in lst:
		ans = 1
	else:
		for i in lst:
			if i in s:
				ans = 2
				break
	sys.stdout.write(str(ans) + '\n')


t = int(input())
s = []
for i in range(t):
	s.append(input())
for i in range(t):
	if int(s[i][-1]) % 2 == 0:
		print(0)
	elif int(s[i][0]) % 2 == 0:
		print(1)
	elif '2' in s[i] or '4' in s[i] or '6' in s[i] or ('8' in s[i]):
		print(2)
	else:
		print(-1)


for s in [*open(0)][1:]:
	print(-all((a := [ord(x) % 2 for x in s[:-1]])) or (a[0] + 1) * a[-1])


t = int(input())
numbers_list = []
for number in range(0, t):
	current_number = int(input())
	numbers_list.append(current_number)

def allodd(n):
	return set(str(n)) - set('13579') == set()
for num in numbers_list:
	if num % 2 == 0:
		print(0)
	elif allodd(num) == True:
		print(-1)
	elif int(str(num)[0]) % 2 == 0:
		print(1)
	else:
		print(2)


def even(num):
	if int(num[-1]) % 2 == 0:
		return 0
	else:
		x = False
		for i in num:
			if int(i) % 2 == 0:
				x = True
		if x:
			if int(num[0]) % 2 == 0:
				return 1
			else:
				return 2
		else:
			return -1
ls = []
for i in range(int(input())):
	ls.append(even(input()))
for i in ls:
	print(i)


for s in [*open(0)][1:]:
	n = int(s)
	last_no = n % 10
	ev = False
	first_digit = 1
	while n > 0:
		if n % 10 % 2 == 0:
			ev = True
		first_digit = n % 10
		n //= 10
	if last_no % 2 == 0:
		print(0)
	elif first_digit % 2 == 0:
		print(1)
	elif ev:
		print(2)
	else:
		print(-1)


def solve(nums):
	hasEven = False
	for n in nums:
		if n % 2 == 0:
			hasEven = True
			break
	if not hasEven:
		return '-1'
	if nums[-1] % 2 == 0:
		return '0'
	if nums[0] % 2 == 0:
		return '1'
	return '2'
ans = []
for _ in range(int(input())):
	ans.append(solve([int(c) for c in input()]))
print(*ans, sep='\n')


t = int(input())
arr = [int(input()) for i in range(t)]
for i in arr:
	j = i
	flag = False
	while j > 0:
		if j % 2 == 0:
			flag = True
			break
		j //= 10
	if flag:
		if i % 2 == 0:
			print(0)
		elif int(str(i)[0]) % 2 == 0:
			print(1)
		else:
			print(2)
	else:
		print(-1)


t = int(input())
arr = []
for _ in range(t):
	arr.append(input())
for number in arr:
	if int(number) % 2 == 0:
		print(0)
		continue
	for (k, el) in enumerate(number):
		if int(el) % 2 == 0:
			l = k
			break
	else:
		print(-1)
		continue
	if l == 0:
		print(1)
	else:
		print(2)


t = int(input())
a = [int(input()) for i in range(t)]
for i in range(t):
	if a[i] % 2 == 0:
		a[i] = 0
	elif a[i] * 10 // 10 ** len(str(a[i])) % 2 == 0:
		a[i] = 1
	else:
		u = 0
		for h in range(len(str(a[i]))):
			if a[i] % 2 == 0:
				u += 1
			a[i] //= 10
		if u == 0:
			a[i] = -1
		else:
			a[i] = 2
for i in range(t):
	print(a[i])


def solutionA():
	n = int(input())
	cases = [int(input()) for _ in range(n)]
	for i in cases:
		if i % 2 == 0:
			print(0)
			continue
		string = str(i)
		if int(string[0]) % 2 == 0:
			print(1)
			continue
		valid = False
		for x in range(len(string) - 1, -1, -1):
			if int(string[x]) % 2 == 0 and x != 0:
				print(2)
				valid = True
				break
		if valid:
			continue
		print(-1)
solutionA()


t = int(input())
l = []

def e(n):
	return int(n) % 2 == 0
for i in range(t):
	s = input()
	if e(s[-1]):
		l.append(0)
	elif e(s[0]):
		l.append(1)
	elif any([e(j) for j in s]):
		l.append(2)
	else:
		l.append(-1)
for i in l:
	print(i)


def f(num):
	count_even = 0
	num = str(num)
	for n in num:
		if int(n) % 2 == 0:
			count_even += 1
	if count_even == 0:
		return -1
	if int(num[len(num) - 1]) % 2 == 0:
		return 0
	if int(num[0]) % 2 == 0:
		return 1
	return 2
nums = [int(input()) for _ in range(int(input()))]
for num in nums:
	print(f(num))


import sys
t = int(sys.stdin.readline())

def get_answer(n):
	if n % 2 == 0:
		return 0
	else:
		s = str(n)
		if int(s[0]) % 2 == 0:
			return 1
		else:
			for i in range(len(s)):
				if int(s[i]) % 2 == 0:
					return 2
			return -1
for _ in range(t):
	n = int(sys.stdin.readline())
	print(get_answer(n))


def EvenCheck(num):
	for i in range(len(num)):
		if int(num[i]) % 2 == 0:
			return True
	return False
inputArray = [str(input()) for i in range(int(input()))]
for i in range(len(inputArray)):
	if int(inputArray[i][-1]) % 2 == 0:
		print(0)
		continue
	if int(inputArray[i][0]) % 2 == 0:
		print(1)
		continue
	elif EvenCheck(inputArray[i]) == False:
		print(-1)
		continue
	else:
		print(2)


times = int(input())
l = []
aa = 1
for _ in range(times):
	a = str(input())
	l.append(a)

def Meven(x):
	if int(x) % 2 == 0:
		return 0
	elif int(x[0]) % 2 == 0:
		return 1
	else:
		for i in x:
			if int(i) % 2 == 0:
				return 2
				break
		return -1
for i in l:
	print(Meven(i))


t = int(input())
inputs = [[int(_) for _ in input()] for i in range(t)]
for n in inputs:
	res = 0
	if int(n[-1]) % 2 == 0:
		pass
	elif int(n[0]) % 2 == 0:
		res = 1
	elif any((x in [2, 4, 6, 8] for x in n)):
		res = 2
	else:
		res = -1
	print(res)


t = int(input())
ans = []
for i in range(t):
	s = input()
	if s.count('0') + s.count('2') + s.count('4') + s.count('6') + s.count('8') == 0:
		ans.append(-1)
	elif int(s[-1]) % 2 == 0:
		ans.append(0)
	elif int(s[0]) % 2 == 0:
		ans.append(1)
	else:
		ans.append(2)
for elem in ans:
	print(elem)


attemps = int(input())
rez_mass = []
for _ in range(attemps):
	ch = input()
	if all((int(x) % 2 != 0 for x in ch)):
		rez_mass.append(-1)
	elif int(ch) % 2 == 0:
		rez_mass.append(0)
	elif int(ch[0]) % 2 == 0:
		rez_mass.append(1)
	else:
		rez_mass.append(2)
print(*rez_mass, sep='\n')


n = int(input())
tlist = []
for i in range(n):
	m = input()
	if int(m) % 2 == 0:
		tlist.append('0')
	elif '2' in m or '4' in m or '6' in m or ('8' in m):
		if m[0] in ['2', '4', '6', '8']:
			tlist.append('1')
		else:
			tlist.append('2')
	else:
		tlist.append('-1')
for _ in tlist:
	print(_)


import sys
input = sys.stdin.readline
t = int(input())
for i in range(t):
	n = input()[:-1]
	if int(n[-1]) % 2 == 0:
		print(0)
	elif int(n[0]) % 2 == 0:
		print(1)
	else:
		containsEven = False
		for j in range(len(n)):
			if int(n[j]) % 2 == 0:
				containsEven = True
		print([-1, 2][containsEven])


ans = ''
for i in range(int(input())):
	n = input()
	c = 0
	if int(n[-1]) % 2 == 0:
		ans += '0' + '\n'
	elif int(n[0]) % 2 == 0:
		ans += '1' + '\n'
	else:
		for i in range(len(n)):
			if int(n[i]) % 2 == 0:
				ans += '2' + '\n'
				c = 1
				break
		if c == 0:
			ans += '-1' + '\n'
print(ans)


for s in [*open(0)][1:]:
	a = [int(x) % 2 for x in s[:-1]]
	print((-1, a[-1] * (a[0] + 1))[0 in a])


for s in [*open(0)][1:]:
	s = s.strip()
	a = [i for (i, c) in enumerate(s) if ord(c) % 2 == 0]
	if len(s) - 1 in a:
		print(0)
	elif not a:
		print(-1)
	elif 0 in a:
		print(1)
	else:
		print(2)


import sys
import bisect
import math
input = lambda : sys.stdin.readline().strip()
mod = 10 ** 9 + 9

def solve():
	s = input()
	even = ['2', '4', '6', '8']
	if not any((x in s for x in even)):
		return -1
	elif s[-1] in even:
		return 0
	elif s[0] in even:
		return 1
	else:
		return 2
t = 1
t = int(input())
for _ in range(t):
	print(solve())


import sys

def input():
	return sys.stdin.readline().rstrip()
t = int(input())
for _ in range(t):
	s = input()
	if int(s[-1]) % 2 == 0:
		print(0)
		continue
	if int(s[0]) % 2 == 0:
		print(1)
		continue
	for i in range(len(s)):
		if int(s[i]) % 2 == 0:
			print(2)
			break
	else:
		print(-1)


import sys
from sys import stdin, stdout
from math import ceil, floor, sqrt, log, log2, log10
from collections import Counter
int_max = float('inf')
int_min = -float('inf')
mod = 10 ** 9 + 7
ANS = []
input = stdin.readline

def solve():
	pass
t = int(input())
for i in range(t):
	n = input().strip()
	if int(n) % 2 == 0:
		print(0)
		continue
	elif int(n[0]) % 2 == 0:
		print(1)
		continue
	else:
		f = 0
		for i in n:
			if int(i) % 2 == 0:
				f = 1
				break
		if f == 0:
			print(-1)
		else:
			print(2)


t = int(input())
ret = []
for i in range(t):
	n = input()
	if int(n[-1]) % 2 == 0:
		ret.append(0)
	elif int(n[0]) % 2 == 0:
		ret.append(1)
	else:
		for s in n:
			if int(s) % 2 == 0:
				ret.append(2)
				break
		else:
			ret.append(-1)
print(*ret, sep='\n')


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	L = [int(d) % 2 == 0 for d in input()[:-1]]
	if L[-1]:
		print(0)
	elif L[0]:
		print(1)
	elif any(L):
		print(2)
	else:
		print(-1)


from sys import stdin, stdout
import sys
import math
import itertools
from collections import defaultdict
sys.setrecursionlimit(10 ** 6)
import re

def main():
	t = int(stdin.readline().strip())
	for j in range(1, t + 1):
		s = stdin.readline().strip()
		even = {'2', '4', '6', '8'}
		if s[-1] in even:
			print(0)
		elif s[0] in even:
			print(1)
		else:
			flag = 0
			for char in s:
				if char in even:
					flag = 1
					break
			if flag == 1:
				print(2)
			else:
				print(-1)
main()


from sys import stdin

def solve():
	results = []
	for _ in range(int(stdin.readline().strip())):
		N = int(stdin.readline().rstrip())
		if N % 2 == 0:
			results.append(0)
			continue
		n = str(N)
		S = {'0', '2', '4', '6', '8'}
		ans = -1
		if n[0] in S:
			results.append(1)
			continue
		ans = -1
		for i in range(len(n)):
			if n[i] in S:
				ans = 2
				break
		results.append(ans)
	print('\n'.join(map(str, results)))
solve()


import sys
input = sys.stdin.readline

def solution(s):
	if int(s[-1]) & 1 == 0:
		return 0
	if int(s[0]) & 1 == 0:
		return 1
	for t in s:
		if int(t) & 1 == 0:
			return 2
	return -1
T = int(input())
for _ in range(T):
	s = input().rstrip()
	print(solution(s))


import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')
inp = lambda : list(map(int, sys.stdin.readline().rstrip('\r\n').split()))
tc = 1
tc = int(input())
for _ in range(tc):
	s = input()
	if ord(s[-1]) % 2 == 0:
		print(0)
		continue
	if ord(s[0]) % 2 == 0:
		print(1)
		continue
	flag = True
	for i in s:
		if ord(i) % 2 == 0:
			print(2)
			flag = False
			break
	if flag:
		print(-1)


t = int(input())
answers = []
for i in range(t):
	n = input()
	if int(n[-1]) % 2 == 0:
		answers.append(0)
	elif int(n[0]) % 2 == 0:
		answers.append(1)
	elif len([x for x in n if int(x) % 2 == 0]):
		answers.append(2)
	else:
		answers.append(-1)
for i in answers:
	print(i)


ans = ''
for _ in range(int(input())):
	n = int(input())
	hasEven = False
	temp = n
	while temp >= 1:
		if temp % 2 == 0:
			hasEven = True
			break
		temp //= 10
	if str(n)[-1] == '2' or str(n)[-1] == '4' or str(n)[-1] == '6' or (str(n)[-1] == '8'):
		ans += '0\n'
	elif str(n)[0] == '2' or str(n)[0] == '4' or str(n)[0] == '6' or (str(n)[0] == '8'):
		ans += '1\n'
	elif hasEven:
		ans += '2\n'
	else:
		ans += '-1\n'
print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	L = []
	flag = 0
	if n % 2 == 0:
		print(0)
	else:
		while n > 0:
			if flag == 0 and n % 2 == 0:
				flag = 1
			L.append(n % 10)
			n //= 10
		if L[-1] % 2 == 0:
			print(1)
		elif flag == 0:
			print(-1)
		else:
			print(2)


t = int(input())
for k in range(t):
	n = input()
	cnt = 0
	if int(n[-1]) % 2 == 0:
		print(0)
	elif int(n[0]) % 2 == 0:
		print(1)
	else:
		for i in n:
			if int(i) % 2 == 0:
				print(2)
				cnt = 1
				break
		if cnt == 0:
			print(-1)


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
t = inp()
while t > 0:
	n = insr()
	e = -1
	for i in range(len(n) - 1, -1, -1):
		if int(n[i]) % 2 == 0:
			e = i
			if i == len(n) - 1:
				break
	if e == len(n) - 1:
		print(0)
	elif e == 0:
		print(1)
	elif e == -1:
		print(-1)
	else:
		print(2)
	t -= 1


a = '2'
b = '4'
c = '6'
d = '8'
t = int(input())
for i in range(t):
	n = input()
	if int(n) % 2 == 0:
		print(0)
	elif len(n) == 1:
		print(-1)
	elif int(n[0]) % 2 == 0:
		print(1)
	elif a in n or b in n or c in n or (d in n):
		print(2)
	else:
		print(-1)


t = int(input())
from sys import stdin
for inp in stdin:
	inp = inp.rstrip()
	if len(inp) == 1 and ord(inp[0]) % 2 != 0:
		print(-1)
	elif ord(inp[-1]) % 2 == 0:
		print(0)
	elif ord(inp[0]) % 2 == 0:
		print(1)
	else:
		for c in range(1, len(inp)):
			if c + 1 < len(inp):
				if ord(inp[c]) % 2 == 0:
					print(2)
					break
			else:
				print(-1)
				break
	if t == 0:
		break
	t -= 1


t = int(input())
ans = []
for _ in range(t):
	s = input()
	hasEvens = False
	for i in s:
		if int(i) % 2 == 0:
			hasEvens = True
	if hasEvens:
		if int(s[-1]) % 2 == 0:
			ans.append(0)
		elif int(s[0]) % 2 == 0:
			ans.append(1)
		else:
			ans.append(2)
	else:
		ans.append(-1)
for i in ans:
	print(i)


arr = []
for i in range(int(input())):
	arr.append(input())

def evenDigit(a):
	for b in a:
		if b % 2 == 0:
			return True
	return False
for x in arr:
	tmp = [int(c) for c in x]
	if tmp[-1] % 2 == 0:
		print(0)
	elif evenDigit(tmp):
		if tmp[0] % 2 == 0:
			print(1)
		else:
			print(2)
	else:
		print(-1)


from copy import deepcopy
t = int(input())
for test_case in range(t):
	n = input()
	s = '2468'
	ans = -1
	if n[-1] in s:
		ans = 0
	elif n[0] in s:
		ans = 1
	else:
		for ch in n:
			if ch in s:
				ans = 2
				break
	print(ans)


T = int(input())
res = []
for _ in range(T):
	n = list(map(int, input()))
	if n[-1] & 1 == 0:
		res.append(0)
		continue
	if n[0] & 1 == 0:
		res.append(1)
		continue
	p = False
	for i in n:
		if i & 1 == 0:
			p = True
			break
	if p:
		res.append(2)
	else:
		res.append(-1)
for i in res:
	print(i)


n = int(input())
li = []
for i in range(n):
	temp = int(input())
	li.append(temp)
for i in range(n):
	temp = str(li[i])
	le = len(temp)
	val = 0
	flag = False
	if int(temp[le - 1]) % 2 == 0:
		print(0)
		flag = True
	elif int(temp[0]) % 2 == 0:
		print(1)
		flag = True
	else:
		for i in range(1, le - 1):
			if int(temp[i]) % 2 == 0:
				flag = True
				print(2)
				break
	if flag == False:
		print(-1)


num = int(input())
listf = []
for x in range(num):
	inp = list(input())
	t = 0
	for r1 in inp:
		if int(r1) % 2 == 0:
			t = 1
	if t == 0:
		listf.append('-1')
	elif int(inp[-1]) % 2 == 0:
		listf.append('0')
	elif int(inp[0]) % 2 == 0:
		listf.append('1')
	else:
		listf.append('2')
for e in listf:
	print(e)


r = int(input())
num = []
for i in range(r):
	num.append(input())
for i in range(r):
	if ord(num[i][len(num[i]) - 1]) % 2 == 0:
		print(0)
	elif ord(num[i][0]) % 2 == 0:
		print(1)
	else:
		flag = True
		for j in num[i]:
			if ord(j) % 2 == 0:
				print(2)
				flag = False
				break
		if flag:
			print(-1)


def proverka(i):
	if i % 2 == 0:
		return 0
	if len(str(i)) == 1:
		return -1
	n = False
	for l in str(i)[:-1]:
		if int(l) % 2 == 0:
			n = True
	if not n:
		return -1
	if int(str(i)[0]) % 2 == 0:
		return 1
	return 2
a = int(input())
chisla = []
for i in range(a):
	chisla.append(int(input()))
for i in chisla:
	print(proverka(i))


for i in range(int(input())):
	(n, x, ans) = (input(), '2468', -1)
	if n[-1] in x:
		ans = 0
	elif n[0] in x:
		ans = 1
	elif sum((1 for i in n if i in x)) > 0:
		ans = 2
	print(ans)


t = int(input())
a = []
for i in range(t):
	i = input()
	a.append(i)
for i in a:
	c = 0
	if int(i[-1]) % 2 == 0:
		print(0)
	elif int(i[0]) % 2 == 0:
		print(1)
	else:
		for j in i:
			if int(j) % 2 == 0:
				print(2)
				c = 1
				break
		if c == 0:
			print(-1)


t = int(input())
c = 0
flag = 1
res = []
for i in range(t):
	x = int(input())
	s = str(x)
	if x % 2 == 0:
		c = 0
		flag = 1
		res.append(c)
	elif int(s[0]) % 2 == 0:
		c = 1
		flag = 1
		res.append(c)
	else:
		l = []
		for j in range(len(s)):
			if int(s[j]) % 2 == 0:
				c = 2
				flag = 1
				break
			else:
				flag = 0
				continue
		if flag == 1:
			res.append(c)
		else:
			res.append(-1)
for i in res:
	print(i)


t = int(input())
for i in range(t):
	n = input()
	nn = int(n)
	flag = 0
	if nn % 2 == 0:
		print(0)
	elif int(n[0]) % 2 == 0:
		print(1)
	else:
		for j in range(len(n)):
			if int(n[j]) % 2 == 0:
				print(2)
				flag = 1
				break
		if flag != 1:
			print(-1)


for s in [*open(0)][1:]:
	s = s.strip('\n')
	a = int(s)
	if a % 2 == 0:
		print(0)
	else:
		(e, o) = (0, 0)
		for i in s:
			i = int(i)
			if i % 2 == 0:
				e += 1
			else:
				o += 1
		if e > 0:
			cnt = 0
			(a, b) = (s[0], s[-1])
			(a, b) = (int(a), int(b))
			if a % 2 != 0:
				cnt += 1
			if b % 2 != 0:
				cnt += 1
			print(cnt)
		else:
			print(-1)


def findeven(innum):
	innum = str(innum)
	for i in range(len(innum)):
		if int(innum[i]) % 2 == 0:
			return i + 1
	else:
		return False
n = int(input())
anslist = []
for x in range(n):
	num = int(input())
	strnum = str(num)
	evenpos = findeven(num)
	if not evenpos:
		anslist.append(-1)
	elif int(strnum[len(strnum) - 1]) % 2 == 0:
		anslist.append(0)
	elif evenpos == 1:
		anslist.append(1)
	elif evenpos > 1:
		anslist.append(2)
for i in anslist:
	print(i)


count = int(input())
nums = []

def checkAllOdd(n):
	c = 0
	for i in str(n):
		if int(i) % 2 == 0:
			c += 1
	if c == 0:
		return True
	else:
		return False
for n in range(count):
	nums.append(int(input()))
for i in nums:
	if i % 2 == 0:
		print(0)
	elif len(str(i)) == 1 and i % 2 != 0:
		print(-1)
	elif checkAllOdd(i):
		print(-1)
	else:
		p = 0
		for k in str(i):
			if int(k) % 2 == 0:
				break
			else:
				p += 1
		p += 1
		if p > 2:
			print(2)
		else:
			print(p)


t = int(input())
li = []
for item in range(t):
	f = int(input())
	x = str(f)
	o = 0
	if f % 2 == 0:
		li.append(0)
	elif int(x[0]) % 2 == 0:
		li.append(1)
	else:
		while o <= len(x) - 1:
			if int(x[o]) % 2 == 0:
				li.append(2)
				break
			if o == len(x) - 1:
				li.append(-1)
				break
			o += 1
for i in li:
	print(i)


def solve():
	n = int(input())
	if n % 2 == 0:
		return 0
	if int(str(n)[0]) % 2 == 0:
		return 1
	for i in str(n):
		if int(i) % 2 == 0:
			return 2
	return -1
t = int(input())
ans = []
while t:
	ans.append(str(solve()))
	t -= 1
print('\n'.join(ans))


t = int(input())
r = []
for i in range(t):
	n = int(input())
	l = [int(x) for x in str(n)]
	if int(n) % 2 == 0:
		r.append(0)
	elif l[0] % 2 == 0:
		r.append(1)
	else:
		f = 0
		for j in range(len(l)):
			if l[j] % 2 == 0:
				f = 1
				break
		if f == 0:
			r.append(-1)
		else:
			r.append(2)
for i in range(len(r)):
	print(r[i])


t = int(input())
s = []
for _ in range(t):
	n = int(input())
	s.append(n)

def func(x):
	if x % 2 == 0:
		return 0
	elif len(str(x)) == 1 and x % 2 != 0:
		return -1
	elif len(str(x)) >= 2:
		item = int(str(x)[0])
		if item % 2 == 0:
			return 1
		else:
			q = 0
			for i in str(x):
				if int(i) % 2 == 0:
					q += 1
			if q >= 1:
				return 2
			else:
				return -1
for item in s:
	print(func(item))


n = int(input())
ans = []
for i in range(n):
	txt = [int(a) for a in input()]
	if txt[-1] % 2 == 0:
		ans.append(0)
	elif txt[0] % 2 == 0:
		ans.append(1)
	else:
		k = 0
		for j in txt:
			if j % 2 == 0:
				k += 1
				break
		if k > 0:
			ans.append(2)
		else:
			ans.append(-1)
for i in ans:
	print(i)


import sys
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def LI1():
	return list(map(int1, sys.stdin.readline().split()))

def LLI1(rows_number):
	return [LI1() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline().rstrip()
dij = [(0, 1), (1, 0), (0, -1), (-1, 0)]
inf = 4294967295
md = 998244353

def solve():
	aa = [int(c) for c in SI()]
	if aa[-1] & 1 == 0:
		print(0)
	elif aa[0] & 1 == 0:
		print(1)
	elif any((a & 1 == 0 for a in aa)):
		print(2)
	else:
		print(-1)
for testcase in range(II()):
	solve()


N = int(input())
for _ in range(N):
	a = input()
	fl = False
	for s in '2468':
		if s in a:
			fl = True
	if fl == False:
		print(-1)
	elif a[-1] in '2468':
		print(0)
	elif a[0] in '2468':
		print(1)
	else:
		print(2)


for i in [int(input()) for i in range(int(input()))]:
	if not i % 2:
		print(0)
	elif '2' not in str(i) and '4' not in str(i) and ('6' not in str(i)) and ('8' not in str(i)):
		print(-1)
	else:
		s = list(str(i))
		try:
			a = s.index('2')
		except Exception as e:
			a = 9
		try:
			b = s.index('4')
		except Exception as e:
			b = 9
		try:
			c = s.index('6')
		except Exception as e:
			c = 9
		try:
			d = s.index('8')
		except Exception as e:
			d = 9
		if not min([a, b, c, d]):
			print(1)
		else:
			print(2)


trails = int(input())
answer_list = []
for x in range(trails):
	in_number = int(input())
	number = []
	for s in str(in_number):
		number.append(s)
	if int(number[-1]) % 2 == 0:
		answer = 0
	elif int(number[-1]) % 2 == 1 and int(number[0]) % 2 == 0:
		answer = 1
	else:
		answer = -1
		for d in number:
			if int(d) % 2 == 0:
				answer = 2
	answer_list.append(answer)
for g in answer_list:
	print(g)


t = int(input())
p = []
for i in range(t):
	k = 0
	l1 = list(map(int, input()))
	n = len(l1)
	if int(l1[n - 1]) % 2 == 0:
		p.append(0)
	elif int(l1[0] % 2) == 0:
		p.append(1)
	else:
		for j in l1:
			if int(j) % 2 == 0:
				p.append(2)
				k = 1
				break
		if k == 0:
			p.append(-1)
print(*p, sep='\n')


te = int(input())
lakshy = []
for asde in range(te):
	lakshy.append(int(input()))
for asde in range(te):
	if lakshy[asde] % 2 == 0:
		print(0)
	elif lakshy[asde] // 10 ** (len(str(lakshy[asde])) - 1) % 2 == 0:
		print(1)
	else:
		das = lakshy[asde]
		while das > 0:
			if das % 2 == 0:
				print(2)
				break
			das //= 10
		if das == 0:
			print(-1)


a = int(input())
b = []
for i in range(a):
	b.append(input())
for i in b:
	if int(i[-1]) % 2 == 0:
		print(0)
	elif int(i[0]) % 2 == 0:
		print(1)
	else:
		for j in range(len(i)):
			if int(i[j]) % 2 == 0:
				print(2)
				break
			if j == len(i) - 1:
				print(-1)
				break
			j = j + 1


from sys import stdin, stdout
from collections import defaultdict
input = stdin.readline
from random import randint
import math
import sys
for _ in range(int(input())):
	n = int(input())
	ans = -1
	if n % 2 == 0:
		ans = 0
	elif int(str(n)[0]) % 2 == 0:
		ans = 1
	else:
		for i in range(len(str(n))):
			if int(str(n)[i]) % 2 == 0:
				ans = 2
	print(ans)


def suitable(s):
	count = 0
	for m in str(s):
		if int(m) % 2 == 0:
			count += 1
	if count == 0:
		print(-1)
	elif int(str(s)[-1]) % 2 == 0:
		print(0)
	elif int(str(s)[0]) % 2 == 0:
		print(1)
	else:
		print(2)
t = int(input())
it = []
for i in range(t):
	it.append(int(input()))
for i in it:
	suitable(i)


t = int(input())
i = 0
result = []
while i < t:
	a = int(input())
	n = [int(x) for x in str(a)]
	l = len(n)
	ans = -1
	odd = 1
	if n[l - 1] % 2 == 0:
		ans = 0
	elif n[0] % 2 == 0:
		ans = 1
	else:
		for j in range(1, l - 1):
			if n[j] % 2 == 0:
				odd = 0
				break
		if odd == 0:
			ans = 2
		else:
			ans = -1
	result.append(ans)
	i += 1
for value in result:
	print(value)


def binarize(string):
	out = ''
	for char in string:
		rest = int(char) % 2
		out = out + str(rest)
	return out
t = int(input())
cisla = [0] * t
for i in range(t):
	cislo = binarize(input())
	if cislo.find('0', -1) == len(cislo) - 1:
		cisla[i] = 0
	elif cislo.find('0') == 0:
		cisla[i] = 1
	elif cislo.find('10') != -1:
		cisla[i] = 2
	else:
		cisla[i] = -1
for cislo in cisla:
	print(cislo)


t = int(input())
lan = []
for _ in range(t):
	n = list(map(int, input()))
	flag = True
	for x in n:
		if x % 2 == 0:
			flag = False
			break
		else:
			continue
	if flag == True:
		lan.append(-1)
	elif n[-1] % 2 == 0:
		lan.append(0)
	elif n[0] % 2 == 0:
		lan.append(1)
	else:
		lan.append(2)
print(*lan, sep='\n')


t = int(input())
ch = '2468'
for i in range(t):
	n = input()
	a = 0
	for q in n:
		if q in ch:
			a = 1
			break
	if a == 0:
		print(-1)
	elif n[-1] in ch:
		print(0)
	elif n[0] in ch:
		print(1)
	else:
		print(2)


t = int(input())
for i in range(t):
	s = input()
	even = ['0', '2', '4', '6', '8']
	if s[-1] in even:
		print(0)
	elif s[0] in even:
		print(1)
	else:
		cnt = 0
		for num in even:
			if num in s:
				cnt = 1
				break
		if cnt == 0:
			print(-1)
		else:
			print(2)


t = int(input())
even = '02468'
odd = '13579'
for _ in range(t):
	s = input()
	if s[-1] in even:
		print(0)
	elif s[0] in even:
		print(1)
	else:
		Check = False
		for c in s:
			if c in even:
				print(2)
				Check = True
				break
		if Check == False:
			print(-1)


def main():
	t = int(input())
	for i in range(t):
		n = input()
		if int(n[-1]) % 2 == 0:
			print(0)
		elif int(n[0]) % 2 == 0:
			print(1)
		else:
			for i in n:
				if int(i) % 2 == 0:
					print(2)
					break
			else:
				print(-1)
main()


t = int(input())
for i in range(t):
	n = input()
	if int(n[len(n) - 1]) % 2 == 0:
		print(0)
	elif int(n[0]) % 2 == 0:
		print(1)
	else:
		k = [int(x) % 2 for x in n].count(1)
		if k == len(n):
			print(-1)
		else:
			print(2)


t = int(input())
even = ['2', '4', '6', '8']
for i in range(t):
	s = input()
	l = len(s)
	if s[l - 1] in even:
		print('0')
	elif s[0] in even:
		print('1')
	elif '2' in s or '4' in s or '6' in s or ('8' in s):
		print('2')
	else:
		print('-1')


def _if_int_(num):
	return num % 2 == 0

def _min_num_(n):
	if _if_int_(int(n)):
		return 0
	elif len(n) == 1:
		return -1
	elif _if_int_(int(n[::-1])):
		return 1
	elif '2' in n or '4' in n or '6' in n or ('8' in n):
		return 2
	else:
		return -1
for i in range(0, int(input())):
	print(_min_num_(input()))


for t in range(int(input())):
	s = input()
	if int(s[-1]) % 2 == 0:
		print(0)
		continue
	if int(s[0]) % 2 == 0:
		print(1)
		continue
	ans = -1
	for i in s:
		if int(i) % 2 == 0:
			ans = 2
	print(ans)