You are given an array A consisting of N positive integers and a positive integer K.

Find whether there exists a *subset* S of the elements of A such that the product of all elements of S is divisible by K.

Note that a *subset* is obtained by deleting some or no elements without changing the order of the remaining elements.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains two space-separated integers N and K — the number of elements of A and the above mentioned integer K. 
- The second line of each test case contains N space-separated integers A_{1},A_{2},\ldots,A_{N} representing the array A.

------ Output Format ------ 

For each test case, print on a new line the answer: YES if there exists a subset S and NO otherwise.

Each character of the output may be printed in either uppercase or lowercase, i.e, the strings Yes, YES, yes, yEs will all be treated as identical.

------ Constraints ------ 

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 100$
$1 ≤ A_{i}, K ≤ 10^{9}$

----- Sample Input 1 ------ 
3
2 2
7 8
5 3
1 1 2 1 1
3 6
7 2 3

----- Sample Output 1 ------ 
YES
NO
YES
----- explanation 1 ------ 
Test case $1$: Consider the subset $S = [8]$. The product of all the elements is $8$ which is divisible by $K = 2$.

Test case $2$: There exists no subset of $A$ such that the product of all elements of the subset is divisible by $K$.

Test case $3$: Consider the subset $S = [2, 3]$. The product of all the elements is $6$ which is divisible by $K = 6$.

Difficulty: EASY
Tags: Mathematics

Starter code:

Solutions:
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	pro = 1
	p = 0
	for i in a:
		pro = pro * i
		if pro % k == 0:
			p = 1
		else:
			continue
	if p == 1:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	d = 1
	for x in a:
		d = d * (x % k)
	if d % k == 0:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	product = 1
	for i in range(n):
		product *= a[i]
		if product % k == 0:
			break
	if product % k == 0:
		print('YES')
	else:
		print('NO')


T = int(input())
while T > 0:
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	for i in a:
		if i % k == 0:
			print('YES')
			break
	else:
		for i in range(n):
			p = 1
			for j in range(i, n):
				p *= a[j]
			if p % k == 0:
				print('YES')
				break
		else:
			print('NO')
	T = T - 1


import math
t = int(input())
for ni in range(t):
	(n, k) = map(int, input().split())
	a = [int(i) for i in input().split()]
	if math.prod(a) % k == 0:
		print('YES')
	else:
		print('NO')


from math import gcd
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	c = [int(x) for x in input().split()]
	ans = 'NO'
	for i in c:
		b //= gcd(b, i)
		if b == 1:
			ans = 'YES'
			break
	print(ans)


t = int(input())
for v in range(0, t, 1):
	nk = input()
	nk = list(map(int, nk.split(' ')))
	a = input()
	a = list(map(int, a.split(' ')))
	product = a[0]
	for v in a:
		product = product * v
	if product % nk[1] == 0:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	f = list(map(int, input().split()))
	g = 1
	c = 0
	for i in f:
		g *= i
		if g % k == 0:
			c = 1
			break
	if c == 1:
		print('YES')
	else:
		print('NO')


import math
t = int(input())
for t in range(t):
	(n, k) = [int(i) for i in input().split()]
	arr = [int(i) for i in input().split()]
	l1 = [[]]
	for i in range(n + 1):
		for j in range(i):
			l1.append(arr[j:i])
	flag = 0
	for i in l1:
		if math.prod(i) % k == 0:
			flag = 1
			print('YES')
			break
	if flag == 0:
		print('NO')


T = int(input())
c = 0
boolean = False
if T < 1 or T > 100:
	print('error')
else:
	for i in range(1, T + 1):
		VAR = input()
		V = VAR.split()
		N = V[0]
		K = V[1]
		if int(K) < 1 or int(N) < 1 or int(N) > 100 or (int(K) > 100000000):
			print('error')
		else:
			ELEMENTS = input()
			A = ELEMENTS.split()
			for i in range(0, int(N)):
				if int(A[i]) < 1 or int(A[i]) > 100000000:
					print('error')
					boolean = True
					break
			if boolean == False:
				product = 1
				for i in A:
					product = product * int(i)
				if product % int(K) == 0:
					print('YES')
				else:
					print('NO')


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


import math
for i in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l1 = [[]]
	for i in range(len(l) + 1):
		for j in range(i):
			l1.append(l[j:i])
	l2 = [i for i in l1 if math.prod(i) % k == 0]
	if len(l2) > 0:
		print('YES')
	else:
		print('NO')


import math
for i in range(int(input())):
	(N, K) = map(int, input().split())
	listA = list(map(int, input().split()))
	if math.prod(listA) % K == 0:
		print('YES')
	else:
		print('NO')


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


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	p = 1
	for e in a:
		p *= e
	print('YES' if p % k == 0 else 'NO')


for i in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	fl = 0
	p = 1
	for j in a:
		p *= j
	if p % k == 0:
		print('YES')
	else:
		print('NO')


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


t = int(input())
while t > 0:
	(b, c) = input().split()
	a = input().split()
	(b, c) = (int(b), int(c))
	p = 1
	for i in a:
		p *= int(i)
	if p % c == 0:
		print('YES')
	else:
		print('NO')
	t -= 1


def ans(n, k, l):
	temp = 1
	for i in l:
		temp = temp * i
		if temp % k == 0:
			print('YES')
			return
	print('NO')
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	ans(n, k, l)


t = int(input())
for x in range(t):
	(n, k) = tuple([int(i) for i in input().split()])
	a = [int(c) for c in input().split()]
	pr = 1
	for i in a:
		pr *= i
	if pr % k == 0:
		print('YES')
	else:
		print('NO')


a = int(input(''))
for i in range(a):
	(N, K) = [int(x) for x in input('').split()]
	T = [int(x) for x in input('').split()]
	k = list(T)
	c = 1
	for j in range(0, len(k)):
		c = c * k[j]
	if c % K == 0:
		print('YES')
	else:
		print('NO')


T = int(input())
while T:
	T -= 1
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	c = 1
	for i in a:
		if not c * i % k:
			print('YES')
			break
		c *= i
	else:
		print('NO')


import math
for i in range(int(input())):
	(x, y) = map(int, input().split())
	a = list(map(int, input().split()))
	n = a[0]
	for i in range(1, x):
		n *= a[i]
		if n % y == 0:
			break
	if n % y == 0:
		print('YES')
	else:
		print('NO')


import math
for i in range(int(input())):
	flag = False
	(n, k) = map(int, input().split())
	lst = [int(lst) for lst in input().split()]
	for i in lst:
		k = k // math.gcd(k, i)
	if k == 1:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	(n, k) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	p = 1
	for i in l:
		p = p * i
	if p % k == 0:
		print('YES')
	else:
		print('NO')


t = int(input())
ctr = 0
while True:
	if t == ctr:
		break
	ctr += 1
	m = input()
	n = input()
	ar1 = m.split()
	ar2 = n.split()
	ar1 = [int(x) for x in ar1]
	ar2 = [int(x) for x in ar2]
	k = int(1)
	for x in ar2:
		k *= x
	k2 = 0
	for x in ar2:
		if x % ar1[1] == 0:
			k2 = 1
	if k2 == 1:
		print('YES')
	elif k % ar1[1] == 0:
		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:
	inp = [int(i) for i in input().split(' ')]
	n = inp[0]
	k = inp[1]
	arr = [int(i) for i in input().split(' ')]
	for i in range(n):
		k2 = int(k / gcd(arr[i], k))
		k = k2
	if k == 1:
		print('YES')
	else:
		print('NO')
	t -= 1


cases = int(input())
for case in range(cases):
	(n, k) = list(map(int, input().split()))
	array = list(map(int, input().split()))
	product = 1
	for num in array:
		product *= num
	if product % k == 0:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, k) = map(int, input().split(' '))
	l = list(map(int, input().split(' ')))
	pdt = 1
	for i in l:
		pdt *= i
		if pdt % k == 0:
			print('YES')
			break
	else:
		print('NO')


t = int(input())
while t:
	t -= 1
	(n, k) = [int(x) for x in input().split()]
	l = list(map(int, input().split()))
	f = 1
	for i in l:
		f = f * i
	if f % k == 0:
		print('YES')
	else:
		print('NO')


def gcd(n1, n2):
	if n1 % n2 == 0:
		return n2
	return gcd(n2, n1 - n1 // n2 * n2)
for i in range(int(input())):
	(n, k) = map(int, input().split())
	a = map(lambda x: gcd(x, k), map(int, input().split()))
	pr = 1
	for elem in a:
		pr = pr * elem
	if pr % k == 0:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, k) = list(map(int, input().split(' ')))
	arr = list(map(int, input().split(' ')))
	pro = 1
	ans = 'NO'
	for i in arr:
		pro *= i
	if pro % k == 0:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	k = 1
	for j in l:
		k = k * j
	if k % b == 0:
		print('YES')
	else:
		print('NO')


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


from itertools import combinations
from math import prod
T = int(input())
while T:
	(n, k) = map(int, input().split())
	print('YES') if prod(list(map(int, input().split()))) % k == 0 else print('NO')
	T -= 1


t = int(input())
while t:
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	x = 1
	y = 0
	for i in a:
		x = x * i
		if x % k == 0:
			y = 1
			break
	if y == 1:
		print('YES')
	else:
		print('NO')
	t = t - 1


import math
for t in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	flag = 0
	for i in range(n):
		s1 = math.prod(a[i:])
		temp = (i + 1) * -1
		s2 = math.prod(a[temp::-1])
		if s1 % k == 0 or s2 % k == 0:
			flag = 1
			break
	if flag:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = [int(i) for i in input().split()]
	s = 1
	for i in arr:
		s *= i
	if s >= k and s % k == 0:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	(N, K) = map(int, input().split(' '))
	lis = list(map(int, input().split(' ')))
	ans = 1
	for j in lis:
		ans *= j
	if ans % K == 0:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	(a, b) = map(int, input().split(' '))
	ele = list(map(int, input().split()))
	pro = 1
	for j in range(0, a):
		pro = pro * ele[j]
	if pro % b == 0:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	(x, y) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	c = 0
	t = 1
	for j in range(0, len(l)):
		t *= l[j]
		if t % y == 0:
			c += 1
			break
	if c == 1:
		print('YES')
	else:
		print('NO')


import math as m
z = int(input())
for x in range(z):
	(a, b) = map(int, input().split())
	c = list(map(int, input().split()))
	d = 1
	for i in c:
		d = d * i
	if d % b == 0:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	(n, k) = map(int, input().split())
	l1 = list(map(int, input().split()))
	prod = int(1)
	for i in l1:
		prod *= i
	if prod % k == 0:
		print('YES')
	else:
		print('NO')


t = int(input())
for x in range(t):
	(n, k) = map(int, input().split())
	alist = list(map(int, input().split()))
	p = 1
	for i in alist:
		p *= i
	if p % k == 0:
		print('YES')
	else:
		print('NO')


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split(' '))
	A = list(map(int, input().split(' ')))
	if math.prod(A) % k == 0:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	a = [int(x) for x in input().split()]
	flag = 0
	for i in range(n):
		for j in range(i, n):
			prod = 1
			l = a[i:j + 1]
			for ele in l:
				prod *= ele
			if prod % k == 0:
				flag = 1
				break
		if flag == 1:
			break
	if flag == 1:
		print('YES')
	else:
		print('NO')


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


t = int(input())
while t:
	p = 1
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	for i in a:
		p *= i
	if p % k == 0:
		print('YES')
	else:
		print('NO')
	t -= 1


for t in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	f = 0
	prod = 1
	for i in a:
		prod *= i
		if prod % k == 0:
			f = 1
	if f == 1:
		print('YES')
	else:
		print('NO')