"I'm a fan of anything that tries to replace actual human contact." - Sheldon.
After years of hard work, Sheldon was finally able to develop a formula which would diminish the real human contact.  
He found k$k$ integers n1,n2...nk$n_1,n_2...n_k$ . Also he found that if he could minimize the value of m$m$ such that  ∑ki=1$\sum_{i=1}^k$n$n$i$i$C$C$m$m$i$i$ is even, where m$m$ = ∑ki=1$\sum_{i=1}^k$mi$m_i$, he would finish the real human contact.  
Since Sheldon is busy choosing between PS-4 and XBOX-ONE, he want you to help him to calculate the minimum value of m$m$. 

-----Input:-----
- The first line of the input contains a single integer T$T$ denoting the number of test cases. The 
description of T$T$ test cases follows.
- The first line of each test case contains a single integer k$k$.
- Next line contains k space separated integers n1,n2...nk$n_1,n_2...n_k$ .

-----Output:-----
For each test case output the minimum value of m for which ∑ki=1$\sum_{i=1}^k$n$n$i$i$C$C$m$m$i$i$ is even, where  m$m$=m1$m_1$+m2$m_2$+. . . mk$m_k$   and  0$0$ <= mi$m_i$<= ni$n_i$ .  If no such answer exists print -1.

-----Constraints-----
- 1≤T≤1000$1 \leq T \leq 1000$
- 1≤k≤1000$1 \leq k \leq 1000$
- 1≤ni≤10$1 \leq n_i \leq 10$18$18$

-----Sample Input:-----
1
1
5

-----Sample Output:-----
2

-----EXPLANATION:-----
5$5$C$C$2$2$ = 10 which is even and m is minimum.

Difficulty: HARD
Tags: Implementation

Starter code:

Solutions:
import math
for _ in range(int(input())):
	(k, arr) = (int(input()), sorted(list(map(int, input().split()))))
	if k % 2 == 0:
		print(0)
	else:
		(m, M) = (-1, [])
		for i in range(k):
			if arr[i] % 2 == 0:
				m = 1
				break
		if m == -1:
			for i in range(k):
				if (arr[i] - 1) // 2 % 2 == 0 and arr[i] > 2:
					m = 2
					break
		if m == -1:
			for i in range(k):
				if math.log(arr[i] + 1, 2) != int(math.log(arr[i] + 1, 2)) and arr[i] > 2:
					b = list(bin(arr[i])[2:])
					if '0' in b:
						M.append(pow(2, b[::-1].index('0')))
		print(m) if M == [] else print(min(M))


def find(x):
	j = bin(x)[2:][::-1]
	c = 1
	flag = 0
	for i in range(len(j)):
		if j[i] == '0':
			return pow(2, i)
	return -1
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	g = []
	h = []
	flag = 0
	v = 10 ** 18
	if n % 2 == 0:
		print(0)
	else:
		for i in a:
			x = find(i)
			if x > 0:
				flag = 1
				v = min(v, x)
		if flag == 0:
			print(-1)
		else:
			print(v)


for i in range(int(input())):
	k = int(input())
	l1 = list(map(int, input().split()))
	countodd = 0
	count1 = 0
	l2 = []
	for item in l1:
		if item % 2 == 1:
			countodd += 1
			if item != 1 and item != 3:
				l2.append(item)
	if k % 2 == 0:
		print(0)
	elif countodd % 2 == 0:
		print(1)
	elif countodd != k:
		print(1)
	else:
		flag = 0
		for item in l2:
			c = 1
			while c < item:
				c *= 2
			if c - 1 != item:
				x = 1
				while x & item != 0:
					x = x * 2
				if flag == 0:
					flag = 1
					mins = x
				else:
					mins = min(mins, x)
		if flag == 1:
			print(mins)
		else:
			print(-1)


T = int(input())

def best(t):
	v2 = 0
	while t % 2 == 0:
		v2 += 1
		t = t // 2
	if t == 1:
		return -1
	else:
		return 2 ** v2
for _ in range(T):
	k = int(input())
	L = [int(x) for x in input().split()]
	if k % 2 == 0:
		print(0)
	elif k > 1:
		even = False
		for i in L:
			if i % 2 == 0:
				even = True
				break
		if even:
			print(1)
		else:
			X = []
			for i in L:
				X.append(best(i + 1))
			S = []
			for i in X:
				if i != -1:
					S.append(i)
			if len(S) == 0:
				print(-1)
			else:
				print(min(S))
	else:
		print(best(L[0] + 1))


def fun():
	test = int(input())
	for t in range(test):
		k = int(input())
		arr = list(map(int, input().split()))
		if k & 1:
			even = False
			for i in arr:
				if i % 2 == 0:
					even = True
			if even:
				print(1)
				continue
			ans = pow(10, 20)
			for i in arr:
				if i & i + 1 != 0:
					count = 0
					j = i
					while j:
						if j % 2 == 0:
							break
						count += 1
						j = j // 2
					ans = min(ans, 1 << count)
			if ans > pow(10, 19):
				ans = -1
			print(ans)
		else:
			print(0)
fun()


t = int(input())

def conv(n):
	k = bin(n)
	k = k[2:]
	z = len(k)
	c = '1' * z
	if c == k:
		return False

def find(n):
	x = bin(n)[2:]
	str = ''
	for i in x[::-1]:
		if i == '0':
			str += '1'
			break
		else:
			str += '0'
	return int(str[::-1], 2)
for i in range(t):
	n = int(input())


t = int(input())

def conv(n):
	k = bin(n)
	k = k[2:]
	z = len(k)
	c = '1' * z
	if c == k:
		return False

def find(n):
	x = bin(n)[2:]
	str = ''
	for i in x[::-1]:
		if i == '0':
			str += '1'
			break
		else:
			str += '0'
	return int(str[::-1], 2)
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	a = l[0]
	if n % 2 == 0:
		print(0)
	else:
		flag = 0
		for j in l:
			if j % 2 == 0:
				flag = 1
				break
		if flag == 1:
			print(1)
		else:
			min = 10 ** 24
			for j in l:
				k = conv(j)
				if k != False:
					z = find(j)
					if z < min:
						min = z
			if min == 10 ** 24:
				print(-1)
			else:
				print(min)


import math
t = int(input())
for _ in range(t):
	k = int(input())
	arr = list(map(int, input().split()))
	if k % 2 == 0:
		print(0)
	else:
		m = -1
		arr.sort()
		M = []
		for i in range(k):
			if arr[i] % 2 == 0:
				m = 1
				break
		if m == -1:
			for i in range(k):
				if (arr[i] - 1) // 2 % 2 == 0 and arr[i] > 2:
					m = 2
					break
		if m == -1:
			for i in range(k):
				x = math.log(arr[i] + 1, 2)
				if x != int(x) and arr[i] > 2:
					b = list(bin(arr[i])[2:])
					if '0' in b:
						idx = b[::-1].index('0')
						P = pow(2, idx)
						M.append(P)
		if M == []:
			print(m)
		else:
			print(min(M))