Sherlock is stuck while solving a problem: Given an array $A=\{a_1,a_2,\cdots,a_N\}$, he wants to know if there exists a subset $\mbox{B}$ of this array which follows these statements:

$\mbox{B}$ is a non-empty subset.
There exists no integer $x(x>1)$ which divides all elements of $\mbox{B}$.
There are no elements of $\mbox{B}$ which are equal to another.

Input Format

The first line of input contains an integer, $\mathbf{T}$, representing the number of test cases. Then $\mathbf{T}$ test cases follow. 

Each test case consists of two lines. The first line contains an integer, $N$, representing the size of array $\mbox{A}$. In the second line there are $N$ space-separated integers, $a_1,a_2,\ldots,a_n$, representing the elements of array $\mbox{A}$.

Constraints 

$1\leq T\leq10$ 

$1\leq N\leq100$ 

$1\leq a_i\leq10^5\:\forall1\leq i\leq N$   

Output Format

Print YES if such a subset exists; otherwise, print NO.

Sample Input
3
3
1 2 3
2
2 4
3
5 5 5

Sample Output
YES
NO
NO

Explanation

In the first test case, $\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\}\ \text{and}\ \{1,2,3\}$ are all the possible non-empty subsets, of which the first and the last four satisfy the given condition.

For the second test case, all possible subsets are $\{2\},\{4\},\{2,4\}$. For all of these subsets, $x=2$ divides each element. Therefore, no non-empty subset exists which satisfies the given condition.

For the third test case, the following subsets exist: $\mbox{S}$_{1}$=\{5\},S$_{2}$=\{5,5\},\:\text{and}\:S$_{3}$=\{5,5,5\}$. 
Because the single element in the first subset is divisible by $5$ and the other two subsets have elements that are equal to another, there is no subset that satisfies every condition.

Source: hackerrank | Difficulty: EASY
Tags: Number theory


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


def gcd(testlist):
	if len(testlist) == 1:
		return testlist[0]
	while len(testlist) > 1:
		a = testlist[len(testlist) - 2]
		b = testlist[len(testlist) - 1]
		testlist = testlist[:len(testlist) - 2]
		while a:
			(a, b) = (b % a, a)
		testlist.append(b)
	return abs(b)
maxval = int(input())
for i in range(0, maxval):
	val = int(input())
	vallist = list(map(int, input().split()))
	val = gcd(vallist)
	if val == 1:
		print('YES')
	else:
		print('NO')


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
T = int(input())
for _ in range(T):
	n = int(input())
	a = [int(i) for i in input().split()]
	g = a[0]
	for i in a:
		g = gcd(g, i)
	if g == 1:
		print('YES')
	else:
		print('NO')


def gcd(a, b):
	if a > b:
		(a, b) = (b, a)
	while a > 0:
		(a, b) = (b % a, a)
	return b
T = int(input())
for _ in range(T):
	N = int(input())
	A = [int(_) for _ in input().split()]
	d = A[0]
	for a in A:
		d = gcd(d, a)
	if d == 1:
		print('YES')
	else:
		print('NO')


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

def gcdapp(arr, ind):
	if len(arr) == 1:
		if arr[ind] == 1:
			return 1
		else:
			return 0
	elif ind == len(arr) - 2:
		return gcd(arr[ind], arr[ind + 1])
	return gcd(arr[ind], gcdapp(arr, ind + 1))
testcase = int(input())
for x in range(testcase):
	size = int(input())
	arr = [int(x) for x in input().strip().split(' ')]
	if gcdapp(arr, 0) == 1:
		print('YES')
	else:
		print('NO')


def gcd_num(x, y):
	if x % y is 0:
		return y
	else:
		return gcd_num(y, x % y)

def gcd(array):
	length = len(array)
	if length > 2:
		return gcd_num(gcd(array[:length // 2]), gcd(array[length // 2:]))
	elif length == 1:
		return array[0]
	else:
		return gcd_num(array[0], array[1])
test = int(input())
while test:
	test = test - 1
	n = int(input())
	array = [int(x) for x in input().strip().split(' ')]
	if len(array) == 1:
		print('NO')
		continue
	v = gcd(array)
	if v == 1:
		print('YES')
	else:
		print('NO')


import sys
from fractions import gcd

def main(argv=None):
	if argv is None:
		argv = sys.argv
T = int(input())
for t in range(0, T):
	N = int(input())
	A = list(map(int, input().split(' ')))
	trouve = False
	for i in range(0, len(A)):
		for j in range(i + 1, len(A)):
			if gcd(A[i], A[j]) == 1:
				trouve = True
			if trouve:
				break
		if trouve:
			break
	if trouve:
		print('YES')
	else:
		print('NO')
sys.exit(main())


import itertools

def gcd(iterable):
	nums = tuple(iterable)
	if len(nums) == 0:
		return None
	while len(nums) > 1:
		d = min(nums)
		nums = (d,) + tuple((m for m in (n % d for n in nums) if m != 0))
	return nums[0]

def sherlock(iterable):
	return gcd(iterable) == 1
T = int(input())
for i in range(T):
	N = int(input())
	arr = tuple((int(n) for n in input().strip().split()))
	print('YES' if sherlock(arr) else 'NO')


from itertools import combinations
import functools, fractions

def findsubsets(S, m):
	return set(combinations(S, m))

def coprime(a, b):
	return fractions.gcd(a, b) == 1
t = int(input())
for _ in range(t):
	n = int(input())
	nbs = [int(i) for i in input().split()]
	found = False
	for (a, b) in findsubsets(nbs, 2):
		if coprime(a, b):
			found = True
			break
	print('YES' if found else 'NO')


import fractions

def gcdx(listx):
	gcdx = listx[0]
	for element in range(len(listx)):
		gcdx = fractions.gcd(gcdx, listx[element])
	return gcdx
tcs = int(input())
for tc in range(tcs):
	elems = input()
	sa = input().split(' ')
	sa2 = [int(x) for x in sa]
	if gcdx(sa2) > 1:
		print('NO')
	else:
		print('YES')


def gcd(a, b):
	if b == 0:
		return a
	elif a < b:
		return gcd(b, a)
	else:
		return gcd(a % b, b)
import math
test = int(input())
for i in range(test):
	nu = int(input())
	l = input()
	q = l.split(' ')
	g = 1
	gcf = int(q[0])
	for i in range(len(q) - 1):
		gcf = gcd(gcf, int(q[i + 1]))
		if gcf == 1:
			g = 0
			break
	if g == 0:
		print('YES')
	else:
		print('NO')


import itertools
import fractions

def answer(a):
	if 1 in a:
		return 'YES'
	for r in range(2, len(a)):
		pairs = list(itertools.combinations(a, 2))
		for pair in pairs:
			if fractions.gcd(pair[0], pair[1]) == 1:
				return 'YES'
	return 'NO'
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(answer(a))


import functools

def GCD(a, b):
	a = abs(a)
	b = abs(b)
	while a:
		(a, b) = (b % a, a)
	return b

def GCD_List(arr):
	return functools.reduce(GCD, arr)
for t in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	if GCD_List(a) == 1:
		print('YES')
	else:
		print('NO')


from fractions import gcd
t = int(input())
for test_case in range(t):
	n = int(input())
	values = str(input()).split()
	denom = int(values[0])
	for i in values:
		denom = gcd(denom, int(i))
	if denom == 1:
		print('YES')
	else:
		print('NO')


T = int(input())
import itertools

def gcd(a, b):
	if a == 1 or b == 1:
		return 1
	if a < b:
		(a, b) = (b, a)
	a = a % b
	if not a:
		return b
	return gcd(a, b)
for line in range(T):
	N = int(input())
	A = [int(x) for x in input().split()]
	found = False
	for (c1, c2) in itertools.combinations(range(N), 2):
		if gcd(A[c1], A[c2]) == 1:
			print('YES')
			found = True
			break
	if not found:
		print('NO')


def gcd2(a, b):
	(a, b) = (min(a, b), max(a, b))
	if a == 0:
		return b
	else:
		return gcd2(a, b % a)

def gcd(l):
	if len(l) == 1:
		return l[0]
	else:
		return gcd([gcd2(l[0], l[1])] + l[2:])
T = int(input())
for i in range(T):
	input()
	l = input().split(' ')
	l = [int(i) for i in l]
	if gcd(l) == 1:
		print('YES')
	else:
		print('NO')


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	result = a[0]
	iter = 1
	while iter < len(a):
		result = gcd(result, a[iter])
		iter = iter + 1
	if result == 1:
		print('YES')
	else:
		print('NO')
	t = t - 1


from fractions import gcd
T = int(input())
for Ti in range(T):
	N = int(input())
	A = [int(v) for v in input().split()]
	result = False
	for i in range(N):
		for j in range(i + 1, N):
			result = result or gcd(A[i], A[j]) == 1
	print('YES' if result else 'NO')


def gcd(a, b):
	while b != 0:
		(a, b) = (b, a % b)
	return a
T = int(input())
for q in range(T):
	N = int(input())
	A = [int(i) for i in input().split(' ')]
	res = A[0]
	for x in A:
		res = gcd(x, res)
	if res == 1:
		print('YES')
	else:
		print('NO')


from itertools import combinations

def gcd(a, b):
	while a != b:
		if a > b:
			a -= b
		if b > a:
			b -= a
	return a
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	combos = list(combinations(l, 2))
	ans = 'NO'
	for j in combos:
		x = max(j)
		y = min(j)
		if gcd(x, y) == 1:
			ans = 'YES'
			break
	print(ans)


import itertools
from fractions import gcd

def watson(size, st):
	for (x, y) in itertools.combinations(st, 2):
		if gcd(x, y) == 1:
			return 'YES'
	return 'NO'
for _ in range(int(input())):
	print(watson(int(input()), set(map(int, input().split()))))


T = int(input())

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

def solve(lst):
	for i in range(len(lst)):
		for j in range(i + 1, len(lst)):
			if gcd(lst[i], lst[j]) == 1:
				return 'YES'
	return 'NO'
for _ in range(T):
	input()
	lst = list(map(int, input().split()))
	print(solve(lst))


def gcd_binaire(x, y):
	if x < y:
		(x, y) = (x, y)
	while y != 0:
		tm = x % y
		x = y
		y = tm
	return x

def gcd(tmp):
	if len(tmp) == 1:
		return tmp[0]
	if len(tmp) == 2:
		return gcd_binaire(tmp[0], tmp[1])
	h = int(len(tmp) / 2)
	return gcd_binaire(gcd(tmp[0:h]), gcd(tmp[h:len(tmp)]))

def compute_subS(lst):
	if len(lst) < 1:
		print('NO')
		return
	elif len(lst) == 1:
		if lst[0] == 1:
			print('YES')
		else:
			print('NO')
		return
	res = gcd(lst)
	if res == 1:
		print('YES')
	else:
		print('NO')
	return
t = int(input())
for i in range(t):
	N = int(input())
	lst = input().split()
	for k in range(len(lst)):
		lst[k] = int(lst[k])
	compute_subS(lst)


import itertools

def gcd(a, b):
	if a < b:
		return gcd(b, a)
	if b == 0:
		return a
	return gcd(b, a % b)
T = int(input())
for _ in range(T):
	N = int(input())
	A = [int(i) for i in input().split()]
	if any((gcd(a, b) == 1 for (a, b) in itertools.combinations(A, 2))):
		print('YES')
	else:
		print('NO')


def GCD(x, y):
	if x < y:
		(x, y) = (y, x)
	if x % y == 0:
		return y
	return GCD(x % y, y)

def arrayGCD(ar):
	ar = sorted(list(set(ar)))
	if len(ar) == 1:
		return ar[0]
	result = ar[0]
	for i in range(1, len(ar)):
		if result == 1:
			return result
		result = GCD(result, ar[i])
	return result

def runner():
	t = int(input())
	for i in range(0, t):
		size = int(input())
		s = input()
		s = s.split(' ')
		nums = []
		for n in s:
			nums += [int(n)]
		numsGCD = arrayGCD(nums)
		if numsGCD == 1:
			print('YES')
		else:
			print('NO')
runner()


__author__ = 'danielbaeck'
import math
import itertools

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
t = int(input())
for i in range(t):
	n = int(input())
	gc = 0
	numbers = [int(x) for x in input().split(' ')]
	for x in numbers:
		gc = gcd(gc, x)
	if gc == 1:
		print('YES')
	else:
		print('NO')


def gcd(a, b):
	while a != b:
		if a > b:
			a = a - b
		else:
			b = b - a
	return a
T = int(input())
for i in range(T):
	N = int(input())
	array = input().split(' ')
	flag = 0
	g = int(array[0])
	for j in range(1, len(array)):
		n1 = g
		n2 = int(array[j])
		g = gcd(n1, n2)
		if g == 1:
			flag = 1
			break
	if flag == 1:
		print('YES')
	else:
		print('NO')


def gcd(a, b):
	while 0 < b:
		(a, b) = (b, a % b)
	return a
T = int(input())
yes = 'YES'
no = 'NO'
for t in range(T):
	N = int(input())
	A = [int(s) for s in input().split()]
	if 1 in A:
		print(yes)
		continue
	found = False
	for i in range(N - 1):
		if found:
			break
		for j in range(i + 1, N):
			if gcd(A[j], A[i]) == 1:
				found = True
	if found:
		print(yes)
	else:
		print(no)


cases = int(input())
from itertools import combinations
from fractions import gcd
for case in range(cases):
	length = int(input())
	l = [x for x in map(int, input().split())]
	if 1 in l or any((gcd(a, b) == 1 for (a, b) in combinations(l, r=2))):
		print('YES')
	else:
		print('NO')


from fractions import gcd
from functools import reduce
T = int(input())
for i in range(T):
	N = int(input())
	A = [int(x) for x in input().split(' ')]
	lowest = reduce(gcd, A)
	if lowest == 1:
		print('YES')
	else:
		print('NO')


def GCD(a, b):
	while b != 0:
		(a, b) = (b, a % b)
	return a

def calGcdOfList(alist):
	length = len(alist)
	if length == 1:
		return alist[0]
	gcd = GCD(alist[0], alist[1])
	for i in range(2, length):
		gcd = GCD(gcd, alist[i])
	return gcd
T = int(input())
for _ in range(T):
	N = int(input())
	alist = list(map(int, input().split()))
	if calGcdOfList(alist) == 1:
		print('YES')
	else:
		print('NO')


import fractions, functools, sys
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	A = list(map(int, sys.stdin.readline().split()))
	gcd = functools.reduce(fractions.gcd, A)
	print('YES' if gcd == 1 else 'NO')


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
T = int(input())
for i in range(T):
	arlength = int(input())
	sarr = str(input()).split(' ')
	iarr = list()
	for m in range(arlength):
		iarr.append(int(sarr[m]))
	count = 0
	n = 0
	for k in range(arlength):
		if iarr[k] != 1:
			for l in range(k, arlength):
				if gcd(iarr[l], iarr[k]) == 1:
					n = 1
					print('YES')
					break
		if n == 1:
			break
	if n == 0:
		print('NO')


def gcd(a, b):
	if a % b == 0:
		return b
	elif a < b:
		return gcd(b, a)
	else:
		return gcd(b, min(a % b, a - a % b))

def func(A):
	rt = A[0]
	for i in A:
		rt = gcd(rt, i)
		if rt == 1:
			return 'YES'
	return 'NO'
for i in range(int(input())):
	input()
	print(func([int(i) for i in input().split()]))


from fractions import gcd
t = int(input())
for _ in range(t):
	found = 'NO'
	n = int(input())
	a = input().split(' ')
	for i in range(n - 1):
		for j in range(i + 1, n):
			if gcd(int(a[i]), int(a[j])) == 1:
				found = 'YES'
	print(found)


def gcd(a, b):
	if a % b == 0:
		return b
	else:
		return gcd(b, a % b)
test = int(input())
for t in range(test):
	n = int(input())
	a = list(map(int, input().split()))
	j = a[0]
	val = False
	for i in a:
		j = gcd(j, i)
		if j == 1:
			val = True
			break
	if val:
		print('YES')
	else:
		print('NO')


import fractions
for x in range(int(input())):
	N = int(input())
	A = {int(a) for a in input().split()}
	while len(A) > 1:
		A.add(fractions.gcd(A.pop(), A.pop()))
	print('YES' if A.pop() == 1 else 'NO')


def gcd(a, b):
	if a != 0 and b != 0:
		return gcd(b, a % b)
	else:
		return a + b
testCases = int(input())
for _ in range(testCases):
	N = int(input())
	array = [int(elem) for elem in input().split()]
	try:
		for index_1 in range(N):
			for index_2 in range(index_1 + 1, N):
				if gcd(array[index_1], array[index_2]) == 1:
					print('YES')
					raise TypeError
	except TypeError:
		continue
	print('NO')


import fractions
t = int(input())
for _ in range(t):
	input()
	g = 0
	for i in input().split(' '):
		g = fractions.gcd(g, int(i))
	print('YES' if g == 1 else 'NO')


from fractions import gcd
T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	if N == 1:
		print('NO')
	else:
		r = gcd(A[0], A[1])
		i = 2
		while r != 1 and i < N:
			r = gcd(r, A[i])
			i += 1
		if r == 1:
			print('YES')
		else:
			print('NO')


import functools

def gcd(a, b):
	while b != 0:
		(a, b) = (b, a % b)
	return a
for _ in range(int(input())):
	N = int(input())
	Array = list(map(int, input().split()))
	if functools.reduce(gcd, list(map(int, Array))) == 1:
		print('YES')
	else:
		print('NO')


from fractions import gcd
c = int(input())
for i in range(0, c):
	(n, a, x, d, flag) = (input(), [], 0, 0, 'NO')
	t = input()
	a = t.split()
	a.sort(key=int)
	while (x < len(a) - 1) & (flag == 'NO'):
		r = gcd(int(a[0]), int(a[x + 1]))
		if int(r) == 1:
			flag = 'YES'
		x = x + 1
	print(flag)


def gcd(a: int, b: int):
	if b == 0:
		return a
	return gcd(b, a % b)
T = int(input())
for i in range(T):
	N = int(input())
	A = [int(x) for x in input().split(' ')]
	my_gcd = 0
	for x in A:
		my_gcd = gcd(my_gcd, x)
	if my_gcd == 1:
		print('YES')
	else:
		print('NO')


from functools import reduce
from fractions import gcd
T = int(input())
for _ in range(T):
	input()
	print('YES') if reduce(gcd, map(int, input().split())) == 1 else print('NO')


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
cases = int(input())
for i in range(cases):
	size = int(input())
	arr = [int(i) for i in input().split()]
	gc = 0
	for val in arr:
		gc = gcd(val, gc)
	if gc == 1:
		print('YES')
	else:
		print('NO')


T = int(input())
for i in range(T):
	N = int(input())
	A = [int(nString) for nString in str(input()).split()]
	t = 0
	for number in A:
		while number != 0:
			number2 = number
			number = t % number2
			t = number2
	if t == 1:
		print('YES')
	else:
		print('NO')


def gcd(a, b):
	minN = min(a, b)
	answer = 1
	for i in range(minN):
		if a % (i + 1) == 0 and b % (i + 1) == 0:
			answer = i + 1
	return answer
T = int(input())
for blah in range(T):
	N = input()
	a = str(input()).split(' ')
	a = [int(x) for x in a]
	GCD = -1
	for j in range(len(a)):
		if GCD == -1:
			GCD = a[j]
		else:
			GCD = gcd(GCD, a[j])
	if GCD == 1:
		print('YES')
	else:
		print('NO')


def gcd(a, b):
	while b != 0:
		t = b
		b = a % b
		a = t
	return a
t = int(input())
for asdfasf in range(t):
	n = int(input())
	tab = list(map(int, input().split()))
	if n == 1 and tab[0] == 1:
		print('YES')
		continue
	for i in range(len(tab)):
		flag = False
		for j in range(i + 1, len(tab)):
			if gcd(tab[i], tab[j]) == 1:
				flag = True
				break
		if flag == True:
			break
	if flag == True:
		print('YES')
	else:
		print('NO')


def gcd(x, y):
	if x < y:
		return gcd(y, x)
	r = x % y
	if r == 0:
		return y
	return gcd(y, r)

def solve():
	l = list(map(int, input().split()))
	L = len(l)
	for i in range(0, L):
		for j in range(i + 1, L):
			if gcd(l[i], l[j]) == 1:
				return 'YES'
	return 'NO'
t = int(input())
for i in range(0, t):
	n = int(input())
	print(solve())


__author__ = 'jeffmcgraw'

def read_line():
	line_list = []
	line_string = input()
	for a in line_string.split(' '):
		b = int(a)
		line_list.append(b)
	return line_list

def test_line():
	num_tests = int(input())
	temp_string = read_line()
	test_string = sorted(temp_string)
	lineout = test_the_line(test_string)
	return lineout

def test_the_line(line_data):
	factors = []
	if 1 in line_data:
		return 'YES'
	for a in range(2, line_data[0] + 1):
		if line_data[0] % a == 0:
			factors.append(a)
	for b in line_data:
		drops = []
		for c in factors:
			if b % c != 0:
				drops.append(c)
		for d in drops:
			factors.remove(d)
		if len(factors) == 0:
			return 'YES'
	return 'NO'

def maine():
	num_tests = int(input())
	for opp_loop in range(num_tests):
		output = test_line()
		print(output)
maine()


import fractions
T = int(input())
for t in range(T):
	N = int(input())
	ai = [int(i) for i in input().split(' ')]
	n = ai[0]
	for i in ai[1:]:
		n = fractions.gcd(n, i)
	if n == 1:
		print('YES')
	else:
		print('NO')


def gcd(a, b):
	if a < b:
		t = a
		a = b
		b = t
	if 0 == a % b:
		return b
	return gcd(b, a % b)
T = int(input())
for i in range(T):
	N = int(input())
	L = list(map(int, input().split()))
	g = L[0]
	for j in range(1, len(L)):
		g = gcd(g, L[j])
	if g == 1:
		print('YES')
	else:
		print('NO')


import fractions
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	e = False
	i = 0
	while i < n and (not e):
		for j in range(i + 1, n):
			if fractions.gcd(a[i], a[j]) == 1:
				e = True
				print('YES')
				break
		i += 1
	if not e:
		print('NO')


import functools

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
T = int(input())
for i in range(T):
	N = int(input())
	res = 'NO'
	numbers = list(map(int, input().split()))
	if len(numbers) > 2:
		res = functools.reduce(lambda x, y: gcd(x, y), numbers)
	if res == 1:
		print('YES')
	else:
		print('NO')


T = int(input())

def gcd(a, b):
	if a % b == 0:
		return b
	return gcd(b, a % b)
for testCase in range(T):
	N = int(input())
	A = [int(i) for i in input().split()]
	for (ai, a) in enumerate(A):
		for b in A[ai:]:
			if gcd(a, b) == 1:
				print('YES')
				break
		else:
			continue
		break
	else:
		print('NO')


from fractions import gcd
t = int(input())
for y in range(t):
	n = int(input())
	line = input().split()
	arr = [int(line[i]) for i in range(n)]
	gc = 0
	for i in range(n):
		gc = gcd(gc, arr[i])
	if gc == 1:
		print('YES')
	else:
		print('NO')


T = int(input())

def gcd(a, b):
	if a < b:
		b = a
		a = b
	while b > 0:
		t = b
		b = a % b
		a = t
	return a

def sherlock_gcd(arr):
	if 1 in arr:
		return 'YES'
	for (i, num) in enumerate(arr[:-1]):
		for (j, other_num) in enumerate(arr[i + 1:]):
			if num != other_num:
				gcd_ret = gcd(num, other_num)
				if gcd_ret == 1:
					return 'YES'
	return 'NO'
for t in range(T):
	N = int(input())
	A = [int(x) for x in str(input()).split()]
	print(sherlock_gcd(A))


import math

def sieve(n):
	m = n + 1
	rn = math.floor(math.sqrt(n)) + 1
	primes = []
	numbs = [True] * m
	numbs[0:2] = [False, False]
	for i in range(4, m, 2):
		numbs[i] = False
	for i in range(3, rn, 2):
		if numbs[i]:
			for a in range(i * i, m, i):
				numbs[a] = False
	for i in range(m):
		if numbs[i]:
			primes.append(i)
	return primes
T = int(input())
N = []
amax = 0
for i in range(T):
	_ = int(input())
	N.append([int(x) for x in input().split()])
	N[i].sort()
	if N[i][-1] > amax:
		amax = N[i][-1]
primes = sieve(amax)
for i in range(T):
	if 1 in N[i]:
		print('YES')
		continue
	common = False
	for p in primes:
		test = 0
		for n in N[i]:
			test += n % p
		if not test:
			common = True
			break
	if common:
		print('NO')
	else:
		print('YES')


def get_input():
	list_of_sets = []
	num_testcases = int(input())
	for testcase in range(num_testcases):
		size_of_array = input()
		list_of_sets.append([int(i) for i in input().split()])
	return list_of_sets

def check_subset(list_of_sets):
	for test_set in list_of_sets:
		subset_exists = 'YES'
		top_val = max(test_set)
		for i in range(2, top_val + 1):
			if len([j for j in test_set if not j % i]) == len(test_set):
				subset_exists = 'NO'
		print(subset_exists)

def run_test():
	testcases = get_input()
	check_subset(testcases)
run_test()


from fractions import gcd

def main():
	T = int(input())
	for _ in range(T):
		N = input()
		ns = list(map(int, input().split()))
		if solve(ns):
			print('YES')
		else:
			print('NO')

def solve(ns):
	for i in ns:
		for j in ns:
			if i == j:
				continue
			if gcd(i, j) == 1:
				return True
	return False
main()


from fractions import gcd
t = int(input())
for i in range(t):
	n = int(input())
	member = input().split(' ')
	st = 'NO'
	for j in range(n):
		for k in range(j, n):
			if gcd(int(member[j]), int(member[k])) == 1:
				st = 'YES'
				break
		if st == 'YES':
			break
	print(st)


from fractions import gcd
from functools import reduce
for _ in range(int(input())):
	input()
	s = [int(x) for x in input().split()]
	if reduce(gcd, s) == 1:
		print('YES')
	else:
		print('NO')


T = int(input())

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

def has_nonmatch(A):
	for i in range(len(A)):
		for j in range(i + 1, len(A)):
			if gcd(A[i], A[j]) == 1:
				return 'YES'
	return 'NO'
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	if A[0] == 1:
		print('YES')
	else:
		print(has_nonmatch(A))


def GCD(a, b):
	while b > 0:
		tmp = b
		b = a % b
		a = tmp
	return a
T = int(input())
for i in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	g = 0
	for j in a:
		g = GCD(g, j)
	if g == 1:
		print('YES')
	else:
		print('NO')


from fractions import gcd
T = int(input())
for i in range(T):
	N = int(input())
	A = input().split(' ')
	A = [int(i) for i in A]
	A.sort()
	if A[0] == 1:
		print('YES')
	elif len(A) == 1:
		print('NO')
	else:
		C = [i for i in range(len(A) - 1) if gcd(A[i], A[i + 1]) <= 1]
		print('YES' if len(C) else 'NO')


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
t = int(input())
while t:
	g = 0
	n = int(input())
	a = input()
	a = a.split()
	x = 0
	for j in a[x:]:
		y = x + 1
		for k in a[y:]:
			g = gcd(int(j), int(k))
		if g == 1:
			print('YES')
			break
	if g != 1:
		print('NO')
	t -= 1


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
t = int(input())
for i in range(t):
	l = int(input())
	inp1 = input().split()
	inp = [int(x) for x in inp1]
	j = 0
	k = 0
	task = ''
	while k < l:
		while j < l and j != k:
			if gcd(inp[j], inp[k]) == 1:
				print('YES')
				task = 'done'
				break
			j += 1
		if task == 'done':
			break
		k += 1
	if task != 'done':
		print('NO')


from sys import stdin
from math import sqrt
cases_count = int(stdin.readline())
for case_number in range(cases_count):
	set_size = int(stdin.readline())
	elements = list(map(int, stdin.readline().split()))
	element_max = max(elements)
	divisor_max = element_max
	if 1 in elements:
		print('YES')
		continue
	for divisor in range(2, divisor_max + 1):
		elements_trial = list(filter(lambda i: i % divisor, elements))
		if 0 == len(elements_trial):
			print('NO')
			break
	else:
		print('YES')


from itertools import combinations
from fractions import gcd
for t in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	x = [comb for comb in combinations(a, 2)]
	for i in x:
		if gcd(i[0], i[1]) == 1:
			print('YES')
			break
	else:
		print('NO')


import fractions
row = int(input())
for i in range(row):
	flag = True
	input()
	l = input().split()
	l = list(map(int, l))
	i1 = i2 = 0
	fr = l[0]
	while i1 < len(l):
		while i2 < i1:
			fr = fractions.gcd(fr, l[i2])
			if fr == 1:
				print('YES')
				flag = False
				break
			i2 += 1
		if flag == False:
			break
		i1 += 1
	if flag == True:
		print('NO')


from fractions import gcd

def solve(case):
	for i in range(len(case) - 1):
		if gcd(case[i], case[i + 1]) == 1:
			return 'YES'
	return 'NO'
cases = int(input())
for _ in range(cases):
	n = input()
	case = [int(x) for x in input().split()]
	print(solve(case))


def hasSubset(n):
	sub = []
	d = None
	for a in n:
		sub.append(a)
		if d == None:
			d = []
			for i in range(a, 1, -1):
				if a % i == 0:
					d.append(i)
		else:
			for i in d:
				if a % i != 0:
					d.remove(i)
	return len(d) == 0
t = int(input())
for _ in range(t):
	input()
	n = [int(x) for x in input().split()]
	print('YES' if hasSubset(n) else 'NO')


import math
import sys

def checkforgcd(A, B):
	for k in range(2, 50):
		if (A % k == 0) & (B % k == 0):
			return 1
	return 0
T = int(input())
for i in range(T):
	N = int(input())
	A = str(input()).split()
	A = list(A)
	B = [0] * N
	for i in range(N):
		B[i] = int(A[i])
	B = sorted(B)
	gcd = B[0]
	for i in range(N):
		if gcd == 1:
			print('YES')
			break
		elif checkforgcd(B[i], gcd) == 1:
			pass
		elif B[i] % gcd != 0:
			print('YES')
			break
		if i == N - 1:
			print('NO')


def get_gcd(a, b):
	if a % b == 0:
		return b
	else:
		return get_gcd(b, a % b)
T = int(input())
for test in range(T):
	N = int(input())
	A = [int(x) for x in input().split()]
	gcd = A[0]
	for el in A[1:]:
		gcd = get_gcd(gcd, el)
	if gcd == 1:
		print('YES')
	else:
		print('NO')


from fractions import gcd

def sherlockAndGcd(A):
	for i in A:
		if 1 in i:
			print('YES')
		else:
			B = [n for n in i for m in i if gcd(n, m) == 1]
			print('YES' if len(B) else 'NO')
cases = int(input())
A = []
for i in range(cases):
	int(input())
	A.append([int(j) for j in input().strip().split()])
sherlockAndGcd(A)


from fractions import gcd

def main():
	T = int(input())
	for t in range(T):
		n = input()
		l = [int(x) for x in input().split()]
		print(check(l))

def check(l):
	s = [[]]
	for x in l:
		s = [e + [x] for e in s]
		for subset in s:
			if len(subset) <= 1:
				continue
			g = gcd(subset[0], subset[1])
			if g == 1:
				return 'YES'
			for i in subset[2:]:
				g = gcd(g, i)
				if g == 1:
					return 'YES'
	return 'NO'
main()


import fractions
t = int(input())
for _ in range(t):
	n = int(input())
	the_list = list(map(int, input().split()))
	answer_existed = False
	for index in range(n):
		if the_list[index] == 1:
			answer_existed = True
			break
		else:
			for index2 in range(index + 1, n):
				if fractions.gcd(the_list[index], the_list[index2]) == 1:
					answer_existed = True
					break
	if answer_existed:
		print('YES')
	else:
		print('NO')


from functools import reduce

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)
for case in range(int(input())):
	input()
	A = map(int, input().split())
	result = reduce(gcd, A) == 1
	print('YES' if result else 'NO')


import sys
from fractions import gcd

def gcd_all(numbers):
	res = 0
	for n in numbers:
		res = gcd(res, n)
	return res

def main():
	T = int(sys.stdin.readline())
	for _ in range(T):
		N = int(sys.stdin.readline())
		A = [int(x) for x in sys.stdin.readline().split()]
		if gcd_all(A) == 1:
			print('YES')
		else:
			print('NO')
main()


from functools import reduce

def gcd(a, b):
	if a == 0:
		return b
	else:
		return gcd(b % a, a)
inputs = int(input())
for _ in range(inputs):
	input()
	x = [int(x) for x in input().split(' ')]
	if reduce(gcd, x) == 1:
		print('YES')
	else:
		print('NO')


import fractions
import functools
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	r = functools.reduce(fractions.gcd, a)
	if r == 1:
		print('YES')
	else:
		print('NO')


from fractions import gcd

def calc(n, ints):
	for i in range(n):
		for j in range(n):
			gcdNum = gcd(ints[i], ints[j])
			if gcdNum == 1:
				return 'YES'
	return 'NO'
t = int(input())
for i in range(t):
	print(calc(int(input()), list(map(int, input().split(' ')))))


def all_divisors(n):
	div = []
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			div += [i, n // i]
	return set(div)

def sherlock(a):
	a = sorted(a)
	divisors = all_divisors(a[0])
	for i in a[1:]:
		divisors = divisors.intersection(all_divisors(i))
		if len(divisors) == 1:
			return True
	return False
T = int(input())
for _ in range(T):
	N = int(input())
	a = [int(x) for x in input().split()]
	if sherlock(a):
		print('YES')
	else:
		print('NO')


from fractions import gcd
t = int(input())

def do_stuff():
	n = int(input())
	nums = set(map(int, input().split()))
	for elem in nums:
		for elem2 in nums:
			if gcd(elem, elem2) == 1:
				print('YES')
				return
	print('NO')
for _ in range(t):
	do_stuff()


from fractions import gcd
T = int(input())
for _ in range(T):
	N = int(input())
	A = input().split(' ')
	A = list(map(int, A))
	set_gcd = 0
	for i in range(N):
		set_gcd = gcd(set_gcd, A[i])
	if set_gcd == 1:
		print('YES')
	else:
		print('NO')


from fractions import gcd
T = int(input())
for case_id in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	if 1 in A:
		print('YES')
	else:
		g = 0
		for i in range(N):
			g = gcd(g, A[i])
		if g == 1:
			print('YES')
		else:
			print('NO')


def if_exists(A):
	for divisor in range(2, min(A) + 1):
		if not sum([x % divisor for x in A]):
			print('NO')
			return
	print('YES')
for i in range(int(input())):
	input()
	A = list(map(int, input().split(' ')))
	if_exists(A)


T = int(input())
for case_i in range(T):
	N = int(input())
	A = input().split()
	state = []
	for x in range(2, 100000):
		state.append(all((int(i) % x == 0 for i in A)))
	if any(state) == True:
		print('NO')
	else:
		print('YES')


from fractions import gcd
from itertools import combinations
for case in range(int(input())):
	input()
	A = [int(x) for x in input().split()]
	gc = 0
	for x in A:
		gc = gcd(gc, x)
	if gc == 1:
		print('YES')
	else:
		print('NO')


from fractions import gcd
__author__ = 'lucas'

def process_gcd(A):
	A.sort()
	for i in range(len(A)):
		test_i = A[i]
		for j in range(i + 1, len(A)):
			test_j = A[j]
			if gcd(test_j, test_i) == 1:
				return 'YES'
	return 'NO'

def main():
	trials = int(input())
	for trial in range(trials):
		N = int(input())
		A = [int(i) for i in input().split(' ')]
		print(process_gcd(A))
main()


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

def gcdl(lst):
	res = 0
	for el in lst:
		res = gcd(res, el)
	return res
t = int(input())
for i in range(t):
	n = input()
	lst = list(map(int, input().split()))
	if gcdl(lst) == 1:
		print('YES')
	else:
		print('NO')


from fractions import gcd
T = int(input())
for i in range(T):
	N = int(input())
	A = [int(x) for x in input().split()]
	A = set(A)
	done = False
	if 1 in A:
		print('YES')
		continue
	for i in A:
		if done:
			break
		for j in A:
			if gcd(i, j) == 1:
				print('YES')
				done = True
				break
	if done:
		continue
	print('NO')


import fractions

def has_coprime_subset(numlist):
	tmplist = sorted(numlist)
	lcm = tmplist[0]
	if lcm == 1:
		return True
	for i in range(1, len(tmplist)):
		if tmplist[i] == tmplist[i - 1]:
			continue
		gcd = fractions.gcd(lcm, tmplist[i])
		if gcd == 1:
			return True
		lcm *= tmplist[i] // gcd
	return False
t = int(input())
for i in range(t):
	n = int(input())
	ns = map(int, input().strip().split())
	if has_coprime_subset(ns):
		print('YES')
	else:
		print('NO')


from fractions import gcd
import itertools
for test in range(int(input())):
	_ = input()
	a = [int(i) for i in input().split(' ')]
	subExists = False
	for (a, b) in itertools.combinations(a, 2):
		if gcd(a, b) == 1:
			subExists = True
	print('YES' if subExists else 'NO')


import fractions
from functools import reduce
for _ in range(int(input())):
	input()
	input_array = [int(x) for x in input().split()]
	print('NO' if reduce(fractions.gcd, input_array) != 1 else 'YES')


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
t = int(input())
for k in range(t):
	n = int(input())
	a = [int(item) for item in input().strip().split()]
	flag = False
	for i in range(n):
		for j in range(i, n):
			if gcd(a[i], a[j]) == 1:
				flag = True
				break
		if flag:
			break
	if flag:
		print('YES')
	else:
		print('NO')


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

def check_arr(arr):
	if len(arr) == 1:
		if arr[0] == 1:
			return True
		else:
			return False
	elif gcd(arr[0], arr[1]) == 1:
		return True
	else:
		return False

def solve(input_list):
	acc = []
	for j in range(len(input_list)):
		acc.append(input_list[j])
		if check_arr(acc):
			return True
		for t in range(j + 1, len(input_list)):
			acc.append(input_list[t])
			if check_arr(acc):
				return True
			else:
				acc.pop()
		acc.clear()
	return False
no_of_test_cases = int(input())
for i in range(no_of_test_cases):
	no_of_elements = int(input())
	elements = list(map(lambda x: int(x), input().split()))
	if solve(elements):
		print('YES')
	else:
		print('NO')


def gcd(a, b):
	if a == 1 or b == 1:
		return 1
	if a < b:
		temp = a
		a = b
		b = temp
	for w in range(b):
		temp = b - w
		if b % temp == 0 and a % temp == 0:
			return temp
for qwop in range(int(input())):
	input()
	nums = list(map(int, input().split()))
	val = False
	l = len(nums)
	while l > 1:
		temp = gcd(nums[0], nums[1])
		del nums[0]
		del nums[0]
		nums.append(temp)
		l = l - 1
	if nums[0] == 1:
		print('YES')
	else:
		print('NO')


from fractions import gcd
for x in range(int(input())):
	n = int(input())
	b = str(input()).split(' ')
	i = 0
	cd = int(b[i])
	while i < len(b):
		cd = gcd(cd, int(b[i]))
		i += 1
	if cd == 1:
		print('YES')
	else:
		print('NO')