Chef got into a fight with the evil Dr Doof. Dr Doof has decided to destroy all even numbers from the universe using his Evil-Destroy-inator. Chef has $N$ integers with him. To stop Doof, Chef has to find an odd number which is an integer multiple of all $N$ numbers that he has with him. Find if it is possible for Chef to prevent Dr Doof from destroying the even numbers.
Formally, given $N$ positive integers, find if there exists an odd number which is an integer multiple of all the given $N$ numbers. If yes, print "YES", otherwise "NO". You can print any letter in any case.

-----Input-----
- First line contains $T$, number of testcases. Each testcase consists of $2$ lines.
- The first line of each test case consists of a positive integer $N$, denoting the number of positive integers Chef has.
- The second line of each test case contains $N$ space separated integers $A_i$ each denoting an integer that Chef has with him.

-----Output-----
For every test case, if there exists such an odd number, print "YES" on a separate line, otherwise "NO". The judge is case insensitive. That means, your code can print any letter in any case ( "Yes", "yes" or "YES" are all accepted).

-----Constraints-----
- $1 \leq T \leq 10^3$
- $1 \leq N \leq 10^3$
- $1 \leq A_i \leq 10^3$

-----Sample Input-----
2
5
1 2 5 4 3
1
7

-----Sample Output-----
NO
YES

-----Explanation-----
For test $1$: There exists no odd number.
For test $2$: The possible odd numbers can be $7$, $21$, $49$, $315$, …

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	value = arr[0]
	if n != 1:
		for i in arr[1:]:
			value = value * i // gcd(value, i)
	if value % 2 == 0:
		print('NO')
	else:
		print('YES')


t = int(input())
for i in range(t):
	n = int(input())
	q = list(map(int, input().split()))
	p = 0
	for j in q:
		if j % 2 != 0:
			p += 1
	if p == len(q):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().strip().split()))
	c = 0
	for i in range(N):
		if A[i] & 1:
			continue
		else:
			c = 1
			break
	if c == 0:
		print('YES')
	else:
		print('NO')


for t in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()[:n]))
	c = 1
	for i in arr:
		c = c * i
	if c % 2 != 0:
		print('YES')
	else:
		print('NO')


for _ in range(0, int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	cnt = 0
	for i in range(0, n):
		if l[i] % 2 == 0:
			cnt += 1
			print('NO')
			break
	if cnt == 0:
		print('YES')


import numpy
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = numpy.prod(a)
	if s % 2 == 0:
		print('NO')
	else:
		print('YES')


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	flag = True
	for i in l:
		if i % 2 == 0:
			flag = False
			break
	if flag:
		print('YES')
	else:
		print('NO')


import math

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

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

def bs(arr, l, r, x):
	while l <= r:
		mid = l + (r - l) // 2
		if arr[mid] == x:
			return arr[mid]
		elif arr[mid] < x:
			l = mid + 1
		else:
			r = mid - 1
	return -1

def swap(list, pos1, pos2):
	(list[pos1], list[pos2]) = (list[pos2], list[pos1])
	return list
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	f = 0
	for i in range(n):
		if a[i] % 2 == 0:
			f = 1
	if f:
		print('NO')
	else:
		print('YES')


for u in range(int(input())):
	flag = 0
	n = int(input())
	lst = list(map(int, input().split()))
	for i in range(n):
		if lst[i] % 2 == 0:
			flag = 1
			break
	if flag == 0:
		print('YES')
	else:
		print('NO')


try:
	t = int(input())
	for _ in range(t):
		n = int(input())
		p = 1
		a = [int(x) for x in input().split()]
		for item in a:
			p = p * item
		if p % 2 == 0:
			print('NO')
		else:
			print('YES')
except:
	pass


test = int(input())
for _ in range(test):
	flag = 0
	N = int(input())
	arr = list(map(int, input().split()))
	for i in arr:
		if i % 2 == 0:
			print('NO')
			flag = 1
			break
	if flag == 0:
		print('YES')


t = int(input())
for l in range(t):
	n = int(input())
	t = list(map(int, input().strip().split()))
	for i in t:
		if i % 2 == 0:
			print('NO')
			break
	else:
		print('YES')


def find_lcm(num1, num2):
	if num1 > num2:
		num = num1
		den = num2
	else:
		num = num2
		den = num1
	rem = num % den
	while rem != 0:
		num = den
		den = rem
		rem = num % den
	gcd = den
	lcm = int(num1 * num2) // int(gcd)
	return lcm
t = int(input())
for num in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	if len(l) == 1:
		if l[0] % 2 == 0:
			print('NO')
		else:
			print('YES')
	else:
		num1 = l[0]
		num2 = l[1]
		lcm = find_lcm(num1, num2)
		for i in range(2, len(l)):
			lcm = find_lcm(lcm, l[i])
		if lcm % 2 == 0:
			print('NO')
		else:
			print('YES')


for testcase in range(int(input())):
	n = int(input())
	sol = [int(i) for i in input().split()]
	main = 1
	a = [0] * 10
	for z in sol:
		if z % 2 == 0:
			main = 0
	if main:
		print('YES')
	else:
		print('NO')


t = int(input())
for t1 in range(t):
	n = int(input())
	l = [int(x) for x in input().split()]
	prod = 1
	for i in l:
		prod = prod * i
	if prod % 2 == 1:
		print('YES')
	else:
		print('NO')


t = int(input())
while t:
	t -= 1
	n = int(input())
	ls = list(map(int, input().split()))
	flag = 1
	for item in ls:
		if item % 2 == 0:
			flag = 0
			break
	if flag == 0:
		print('NO')
	else:
		print('YES')


for i in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	flag = 0
	for j in b:
		if j % 2 == 0:
			flag += 1
			break
	if flag == 0:
		print('YES')
	else:
		print('NO')