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 ≤ T ≤ 10^{3}$
$1 ≤ N ≤ 10^{3}$
$1 ≤ A_{i} ≤ 10^{3}$

----- Sample Input 1 ------ 
2
5
1 2 5 4 3
1
7
----- Sample Output 1 ------ 
NO
YES
----- explanation 1 ------ 
For test $1$: There exists no odd number.

For test $2$: The possible odd numbers can be $7$, $21$, $49$, $315$, ...

Difficulty: EASY
Tags: Number theory

Constructive algorithms

Mathematics

Ad-hoc

Starter code:

Solutions:
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a_odd = list(filter(lambda x: x % 2 != 0, a))
	if len(a_odd) == n:
		print('YES')
	else:
		print('NO')


n = int(input())
for i in range(n):
	n1 = int(input())
	count = 0
	l = list(map(int, input().split()))
	for j in range(n1):
		if l[j] % 2 != 0:
			count += 1
	if count == n1:
		print('YES')
	else:
		print('NO')


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


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


for i in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	for i in a:
		if i % 2 == 0:
			print('NO')
			break
	else:
		print('YES')


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


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


for i in range(int(input())):
	n = int(input())
	N = list(map(int, input().split()))
	c = True
	for i in range(0, int(len(N))):
		if N[i] % 2 == 0:
			print('NO')
			c = False
			break
	if c:
		print('YES')


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


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


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


q = int(input())
for i in range(q):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = []
	for j in l:
		if j % 2 != 0:
			l1.append(j)
	if len(l1) == n:
		print('YES')
	else:
		print('NO')


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


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


for _ in range(int(input())):
	a = int(input())
	list = [int(x) for x in input().split()]
	flag = 0
	for i in list:
		if i % 2 == 0:
			flag = 1
			print('NO')
			break
	if flag == 0:
		print('YES')


for _ in range(int(input())):
	a = int(input())
	list = [int(x) for x in input().split()]
	flag = False
	for i in list:
		if i % 2 == 0:
			flag = True
			print('NO')
			break
	if not flag:
		print('YES')


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


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


t = int(input())
for _ in range(t):
	n = int(input())
	line = input()
	words = line.split()
	nums = [int(w) for w in words]
	for num in nums:
		if num % 2 == 0:
			print('NO')
			break
	else:
		print('YES')


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = [x for x in l if x % 2 == 0]
	if len(l1) >= 1:
		print('NO')
	else:
		print('YES')


goals = int(input())
for distractions in range(goals):
	wife = int(input())
	life = list(map(int, input().split()))
	aim = list(filter(lambda death: death % 2 != 0, life))
	if len(aim) == wife:
		print('YES')
	else:
		print('NO')


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


for tc in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	x = [1 for i in l if i % 2 == 0]
	if len(x) > 0:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	N = int(input())
	L = list(map(int, input().split()))
	for i in L:
		if not i % 2:
			print('NO')
			break
	else:
		print('YES')


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


t = int(input())
for i in range(t):
	n = int(input())
	n1 = list(map(int, input().split()))
	n2 = max(n1)
	c = 0
	for j in range(len(n1)):
		if n1[j] % 2 == 0:
			b = 0
			print('NO')
			break
		else:
			b = 1
	if b == 1:
		print('YES')


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


for i in range(int(input())):
	a = int(input())
	x = [int(i) for i in input().split()]
	k = 1
	for i in range(a):
		k *= x[i]
	if k % 2 == 0:
		print('NO')
	else:
		print('YES')


t = int(input())
for tc in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	p = 1
	for j in range(n):
		p *= a[j]
	if p % 2 == 0:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	lennos = int(input())
	nolist = list(map(int, input().split()))
	count = 0
	for i in nolist:
		if i % 2 != 0:
			count += 1
	if count == lennos:
		print('YES')
	else:
		print('NO')


t = int(input())
while t != 0:
	t = t - 1
	n = int(input())
	a = [int(i) for i in input().split()]
	count = 0
	for i in range(n):
		if a[i] % 2 != 0:
			count += 1
	if count == n:
		print('YES')
	else:
		print('NO')


import typing

def main():
	t = int(input())
	for _ in range(t):
		input()
		numbers = list(map(int, input().split(' ')))
		print('YES' if can_be_doof_stopped(numbers) else 'NO')

def can_be_doof_stopped(values: typing.List[int]) -> bool:
	_lcm = 1
	for value in values:
		_lcm = lcm(_lcm, value)
	return _lcm % 2 == 1

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

def gcd(a: int, b: int) -> int:
	while b != 0:
		(a, b) = (b, a % b)
	return a
main()


t = int(input())
for i in range(t):
	N = int(input())
	A = list(map(int, input().split()))
	has_even = False
	for j in A:
		if j % 2 == 0:
			has_even = True
			break
	if not has_even:
		print('YES')
	else:
		print('NO')


def versus():
	for i in a:
		if i % 2 == 0:
			return 'NO'
	else:
		return 'YES'
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	print(versus())