"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: interview

Starter code:

Solutions:
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())