Chef has a number N, Cheffina challenges the chef to check the divisibility of all the permutation of N by 2. If any of the permutations is divisible by 2 then print 1 else print 0.

-----Input:-----
- First-line will contain $T$, the number of test cases. Then the test cases follow. 
- Each test case contains a single line of input, $N$. 

-----Output:-----
For each test case, output in a single line answer 1 or 0.

-----Constraints-----
- $1 \leq T \leq 10^6$
- $1 \leq N \leq 10^6$

-----Sample Input:-----
2
19
385

-----Sample Output:-----
0
1

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
for i in range(int(input())):
	n = int(input())
	flag = 0
	while n > 0:
		if n % 10 % 2 == 0:
			flag = 1
			break
		n = n // 10
	if flag == 0:
		print(0)
	else:
		print(1)


testcases = int(input())
for i in range(testcases):
	n = input()
	if '2' in n or '4' in n or '6' in n or ('8' in n) or ('0' in n):
		print(1)
	else:
		print(0)


import sys, io, os, math
from math import ceil, log, gcd, inf
from itertools import permutations
mod = 1000000007
mod1 = 998244353

def printlist(n):
	sys.stdout.write(' '.join(map(str, n)) + '\n')
printf = lambda n: sys.stdout.write(str(n) + '\n')

def printns(n):
	sys.stdout.write(str(n))

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

def strinp():
	return sys.stdin.readline()

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

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

def flush():
	return sys.stdout.flush()

def power_two(x):
	return 1 << x

def lcm(a, b):
	return a * b // gcd(a, b)

def solve():
	n = str(intinp())
	for i in n:
		if int(i) % 2 == 0:
			print(1)
			return 0
	print(0)

def main():
	tc = intinp()
	while tc:
		solve()
		tc -= 1
main()


from sys import *
input = stdin.readline
for i in range(int(input())):
	n = int(input())
	while n > 0:
		r = n % 10
		if r % 2 == 0:
			print(1)
			break
		n = n // 10
	else:
		print(0)


def solve(n):
	while n > 0:
		e = n % 10
		if e % 2 == 0:
			return 1
		n = n // 10
	return 0
for _ in range(int(input())):
	n = int(input())
	print(solve(n))


from sys import *
input = stdin.readline
for u in range(int(input())):
	num = int(input())
	while num > 0:
		r = num % 10
		if r % 2 == 0:
			print(1)
			break
		num = num // 10
	else:
		print(0)


for _ in range(int(input())):
	s = input()
	x = '02468'
	for i in x:
		if i in s:
			print(1)
			break
	else:
		print(0)


import sys
input = lambda : sys.stdin.readline()
for _ in range(int(input())):
	k = int(input())
	for i in str(k):
		if int(i) % 2 == 0:
			print('1')
			break
	else:
		print('0')


from sys import *
input = stdin.readline
for u in range(int(input())):
	n = int(input())
	f = 0
	for i in str(n):
		if int(i) % 2 == 0:
			f = 1
			break
	print(f)


for _ in range(int(input())):
	k = input()
	flag = 0
	a = ['0', '2', '4', '6', '8']
	for i in k:
		if i in a:
			flag = 1
			break
	if flag == 1:
		print('1')
	else:
		print('0')


import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')
inp = lambda : list(map(int, sys.stdin.readline().rstrip('\r\n').split()))
from collections import Counter as cc
mod = 10 ** 9 + 7
md = 998244353
tc = 1
(tc,) = inp()
for _ in range(tc):
	(n,) = inp()
	print(1 if any([int(i) % 2 == 0 for i in str(n)]) else 0)


def solution(n):
	while n:
		if n % 10 & 1 == 0:
			return 1
		else:
			n = n // 10
	return 0
for i in range(int(input())):
	n = int(input())
	print(solution(n))


for k in range(int(input())):
	s = input()
	ans = 0
	for p in s:
		if int(p) % 2 == 0:
			ans = 1
			break
	print(ans)


try:

	def check(n):
		while n != 0:
			if n % 10 % 2 == 0:
				return 1
			n //= 10
		return 0
	t = int(input())
	for _ in range(t):
		n = int(input())
		print(check(n))
except EOFError:
	pass


t = int(input())
for s in range(t):
	k = int(input())
	flag = 0
	while k > 0:
		digi = k % 10
		if digi % 2 == 0:
			flag = 1
			break
		k = k // 10
	if flag == 1:
		print(1)
	else:
		print(0)


t = int(input())
while t > 0:
	n = int(input())
	count = 0
	while n > 0:
		r = n % 10
		if r % 2 == 0:
			count = count + 1
			break
		else:
			n = n // 10
	if count == 0:
		print('0')
	else:
		print('1')
	t = t - 1


for _ in range(int(input())):
	r = int(input())
	while r != 0:
		k = r % 10
		if k % 2 == 0:
			print('1')
			break
		r = r // 10
	else:
		print('0')


for _ in range(int(input())):
	ans = 0
	for i in str(input()):
		if i in ['2', '4', '6', '8', '0']:
			ans = 1
			break
	print(ans)


import sys
from math import log2
from itertools import combinations
for _ in range(int(sys.stdin.readline())):
	n = str(sys.stdin.readline())
	n = n[:-1]
	temp = 0
	for i in range(len(n)):
		if int(n[i]) % 2 == 0:
			temp = 1
	if temp:
		print(1)
	else:
		print(0)


n = int(input())
ls = []
for _ in range(n):
	ls.append(int(input()))
for ele in ls:
	ele = str(ele)
	ele = list(ele)
	flag = 0
	for i in ele:
		if int(i) % 2 == 0:
			print('1')
			flag = 1
			break
	if flag == 0:
		print('0')


t = int(input())
for _ in range(t):
	p = input()
	flag = False
	z = ['0', '2', '4', '6', '8']
	for ele in p:
		if ele in z:
			print(1)
			flag = True
			break
	if flag == False:
		print(0)


t = int(input())
for _ in range(0, t):
	n = int(input().strip())
	ok = False
	while n > 0:
		rem = n % 10
		if rem % 2 == 0:
			ok = True
			break
		else:
			n = n // 10
	if ok == True:
		print('1')
	else:
		print('0')