# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* satyam_343

*IceKnight1093, tejas10p*

**Testers:***IceKnight1093*

**Editorialist:**# DIFFICULTY:

1329

# PREREQUISITES:

# PROBLEM:

Given an array A, find a subset whose product is divisible by K or report that none exist.

# EXPLANATION:

Suppose that we had a subset S whose product was divisible by K.

Then, notice that if we add more elements to the subset, its product will still be divisible by K.

So, itâ€™s enough to check whether the product of all the elements is divisible by K.

However, the product of all elements is too large to compute (at least in C/C++).

Instead, notice that we only care about whether the product is divisible by K or not, not what the actual product is.

So, we can just compute A_1\cdot A_2 \cdot \ldots \cdot A_N \pmod K and check whether this is zero or not.

Computing this can be done with a loop as follows:

- Initialize a variable prod = 1.
- For each i from 1 to N, do the following:
- Multiply prod with A_i modulo K, i.e, set prod \to (prod \cdot A_i) \pmod K

- The final value of prod is what we want. Check whether itâ€™s zero or not, and weâ€™re done.

# TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

# CODE:

## Code (Python)

```
for _ in range(int(input())):
n, k = map(int, input().split())
a = list(map(int, input().split()))
prod = 1
for x in a:
prod *= x
prod %= k
print('Yes' if prod == 0 else 'No')
```