You are given an array $a$ consisting of $n$ integers.

In one move, you can choose two indices $1 \le i, j \le n$ such that $i \ne j$ and set $a_i := a_j$. You can perform such moves any number of times (possibly, zero). You can choose different indices in different operations. The operation := is the operation of assignment (i.e. you choose $i$ and $j$ and replace $a_i$ with $a_j$).

Your task is to say if it is possible to obtain an array with an odd (not divisible by $2$) sum of elements.

You have to answer $t$ independent test cases.


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 2000$) — the number of test cases.

The next $2t$ lines describe test cases. The first line of the test case contains one integer $n$ ($1 \le n \le 2000$) — the number of elements in $a$. The second line of the test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 2000$), where $a_i$ is the $i$-th element of $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2000$ ($\sum n \le 2000$).


-----Output-----

For each test case, print the answer on it — "YES" (without quotes) if it is possible to obtain the array with an odd sum of elements, and "NO" otherwise.


-----Example-----
Input
5
2
2 3
4
2 2 8 8
3
3 3 3
4
5 5 5 5
4
1 1 1 1

Output
YES
NO
YES
NO
NO

Difficulty: introductory

Starter code:

Solutions:
for _ in range(int(input())):
    n = int(input())
    ar = list(map(int, input().split()))
    a, b = 0, 0
    for elem in ar:
        if elem % 2 == 0:
            a = 1
        else:
            b = 1
    if sum(ar) % 2 == 1:
        print('YES')
    elif a == 1 == b:
        print('YES')
    else:
        print('NO')

for _ in range(int(input())):
    n = int(input())
    A = list(map(int, input().split()))
    c1, c2 = 0, 0
    for i in A:
        if i % 2:
            c1 += 1
        else:
            c2 += 1
    if c1 == 0:
        print('NO')
    elif c2 == 0:
        if n% 2:
            print('YES')
        else:
            print('NO')
    else:
        print('YES')



import math
from decimal import Decimal
import heapq
import copy
import heapq
from collections import deque
def na():
	n = int(input())
	b = [int(x) for x in input().split()]
	return n,b
 
	
def nab():
	n = int(input())
	b = [int(x) for x in input().split()]
	c = [int(x) for x in input().split()]
	return n,b,c
 
		
def dv():
	n, m = list(map(int, input().split()))
	return n,m
 
 
def da():
	n, m = list(map(int, input().split()))
	a = list(map(int, input().split()))
	return n,m, a 
 
 
def dva():
	
	n, m = list(map(int, input().split()))
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	return n,m,b
 
 
def eratosthenes(n): 
	sieve = list(range(n + 1))
	for i in sieve:
		if i > 1:
			for j in range(i + i, len(sieve), i):
				sieve[j] = 0
	return sorted(set(sieve))
 
 
def lol(lst,k):
	k=k%len(lst)
	ret=[0]*len(lst)
	for i in range(len(lst)):
		if i+k<len(lst) and i+k>=0:
			ret[i]=lst[i+k]
		if i+k>=len(lst):
			ret[i]=lst[i+k-len(lst)]
		if i+k<0:
			ret[i]=lst[i+k+len(lst)]
	return(ret)
def nm():
	n = int(input())
	b = [int(x) for x in input().split()]
	m = int(input())
	c = [int(x) for x in input().split()]
	return n,b,m,c
 
 
def dvs():
	n = int(input())
	m = int(input())
	return n, m 
 

def fact(n):
	tc = []
	ans = {}
	d = 2
	while d * d <= n:
		if n % d == 0:
			tc.append(d)
			n //= d
		else:
			d += 1
	if n > 1:
		tc.append(n)
	for i in tc:
		ans[i] = ans.get(i, 0) + 1
	return ans


for i in range(int(input())):
		n, a = na()
		nech = 0
		s = 0
		for j in a:
			if j % 2 == 1:
				nech += 1
			s += j
		if s % 2 == 1:
			print('YES')
			continue
		if nech == n or nech == 0:
			print('NO')
		else:
			print('YES')


import sys
import math
import itertools
import functools
import collections
import operator


def ii(): return int(input())
def mi(): return map(int, input().split())
def li(): return list(map(int, input().split()))
def lcm(a, b): return abs(a * b) // math.gcd(a, b)
def revn(n): return str(n)[::-1]
def dd(): return collections.defaultdict(int)
def ddl(): return collections.defaultdict(list)
def sieve(n):
    if n < 2: return list()
    prime = [True for _ in range(n + 1)]
    p = 3
    while p * p <= n:
        if prime[p]:
            for i in range(p * 2, n + 1, p):
                prime[i] = False
        p += 2
    r = [2]
    for p in range(3, n + 1, 2):
        if prime[p]:
            r.append(p)
    return r
def divs(n, start=2):
    r = []
    for i in range(start, int(math.sqrt(n) + 1)):
        if (n % i == 0):
            if (n / i == i):
                r.append(i)
            else:
                r.extend([i, n // i])
    return r
def divn(n, primes):
    divs_number = 1
    for i in primes:
        if n == 1:
            return divs_number
        t = 1
        while n % i == 0:
            t += 1
            n //= i
        divs_number *= t
def prime(n):
    if n == 2: return True
    if n % 2 == 0 or n <= 1: return False
    sqr = int(math.sqrt(n)) + 1
    for d in range(3, sqr, 2):
        if n % d == 0: return False
    return True
def convn(number, base):
    newnumber = 0
    while number > 0:
        newnumber += number % base
        number //= base
    return newnumber
def cdiv(n, k): return n // k + (n % k != 0)


t = ii()
for _ in range(t):
    n = ii()
    a = li()
    if all(a[i] & 1 for i in range(n)) and not n & 1 or all(not a[i] & 1 for i in range(n)):
        print('NO')
    else:
        print('YES')

def iinput():
    return [int(x) for x in input().split()]


def main():
    n = int(input())
    data = iinput()
    count = 0
    for i in range(n):
        if data[i] % 2 == 1:
            count += 1
    if count == 0 or (count == n and n % 2 == 0):
        return 'NO'
    else:
        return 'YES'


for t in range(int(input())):
    print(main())


t=int(input())
for _ in range(t):
    n=int(input())
    it=list(map(int,input().split()))
    s=[i for i in it if i%2==1]
    if(len(s)>=1 and (len(s)<n or n%2==1)):
        print("YES")
    else:
        print("NO")


t=int(input())
while(t):
    t-=1
    n=int(input())
    a=list(map(int,input().split()))
    co=0
    for i in a:
        if(i%2):
            co+=1
    if((co==n and n%2==0) or co==0):
        print("NO")
    else:
        print("YES")


t=int(input())
for i in range(t):
    n=int(input())
    a=list(map(int,input().split()))
    odd,even=False,False
    for i in a:
        if i%2==0:
            even=True
        else:
            odd=True
        if odd and even:
            print('YES')
            break
    else:
        if odd and (not even) and n%2==1:
            print('YES')
        else:
            print('NO')


t = int(input())
for zz in range(t):
    n = int(input())
    a = [int(i) for i in input().split()]
    ha = False
    ho = False
    he = False
    for i in a:
        if i % 2 == 1:
            ho = True
        else:
            he = True
    if n % 2 == 0:
        ha = ho and he
    else:
        ha = ho
    if ha:
        print('YES')
    else:
        print('NO')


import math, collections, sys
input = sys.stdin.readline
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    oc = 0
    for i in a:
        oc+=i%2
    if oc:
        if oc%2:
            print("YES")
        else:
            if n-oc:
                print("YES")
            else:
                print("NO")
    else:
        print("NO")

t = int(input())
for _ in range(t):
    n = int(input())
    a = [int(i) for i in input().split()]
    o = 0
    for i in a:
        if i%2 != 0:
            o += 1
    if o == 0:
        print("NO")
    elif o == n and n%2 == 0:
        print("NO")
    elif o == n and n%2 == 1:
        print("YES")
    else:
        print("YES")


def solve(arr,n):
    even = 0
    for i in arr:
        if i%2 == 0:
            even += 1

    if even == n:
        print('NO')
        return
    
    odd = n-even

    if odd == n and n%2 == 0:
        print('NO')
        return
    
    print('YES')

def main():
    t = int(input())
    for i in range(t):
        n = int(input())
        arr = list(map(int,input().split()))
        solve(arr,n)

    
main()


n = int(input())
for i in range(n):
    num = int(input())
    lst = list(map(int, input().split()))
    even = 0
    odd = 0
    for j in lst:
        if j % 2 == 0:
            even+=1
        else:
            odd+=1
    if odd == 0 or (odd == num and num % 2 == 0):
        print("NO")
    else:
        print("YES")



for _ in range(int(input())):
    n = int(input())
    a = [int(i) for i in input().split()]
    
    if sum(a) % 2 == 1:
        print('YES')
    
    
    else:
        par = False
        impar = False
        for i in a:
            if i % 2 == 0:
                par = True
            else:
                impar = True
        if par and impar:
            print('YES')
        else:
            print('NO')
            




for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	if sum(arr)%2 == 1:
		print('YES')
	elif all(ele%2 == 0 for ele in arr):
		print('NO')
	elif all(ele%2 == 1 for ele in arr) and len(arr)%2 == 0:
		print('NO')
	else:
		print('YES')