Borommarachathirat IV (สมเดจพระบรมราชาธราชท 4) was a ruler of the Ayutthaya Kingdom in the 16th century. Borommarachathirat IV decided to create a lottery for his subjects using dice. These are traditional Thai dice and they may have several faces, where each face is rolled with the same probability.
The ruler demands the lottery to be perfectly fair, that is, each of his subjects must have the same probability of winning. The lottery consists of a finite number of rounds of dice rolls and, after each round, it is either decided that there is a winner or that more rounds are required. The dice rolls must follows the following rules:
It is imperative to ensure that each subject has the same chance of winning the lottery. Notice that this is not always possible. For instance, if there are 5 subjects and a single 6-face die, then it is impossible to have a fair lottery. On the other hand, with such a die one can have a fair lottery if the population size is 3, 6, 18, or 36 people, and so on.
Your task in this problem is to write a program to help the ruler decide if it is possible to have a fair lottery with the available dice.
The first line has a single integer T, the number of test cases.
Each test case is given in two lines. The first line has 2 integer, N and K, the amount of people and dice, respectively. The second line has K integers, the i-th integer fi is the number of faces in the i-th die.
*Limits*
For each test case, print a single line containing a single character. Print _Y_ if it is possible to make the lottery; otherwise, print _N_.
## Input
The first line has a single integer T, the number of test cases.Each test case is given in two lines. The first line has 2 integer, N and K, the amount of people and dice, respectively. The second line has K integers, the i-th integer fi is the number of faces in the i-th die.*Limits* 1 ≤ T ≤ 120 1 ≤ N ≤ 1018 0 ≤ K ≤ 105 The sum of K over all test cases will not exceed 6·105 1 ≤ fi ≤ 1018
## Output
For each test case, print a single line containing a single character. Print _Y_ if it is possible to make the lottery; otherwise, print _N_.
[samples]
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case $ k \in \{1, \dots, T\} $:
- $ N_k \in \mathbb{Z}^+ $: number of subjects.
- $ K_k \in \mathbb{Z}^+ $: number of dice.
- $ F_k = (f_{k,1}, f_{k,2}, \dots, f_{k,K_k}) \in (\mathbb{Z}^+)^{K_k} $: face counts of the dice.
**Constraints**
1. $ 1 \le T \le 1000 $
2. $ 1 \le N_k \le 10^9 $
3. $ 1 \le K_k \le 10 $
4. $ 1 \le f_{k,i} \le 100 $ for all $ i \in \{1, \dots, K_k\} $
**Objective**
Determine whether there exists a finite sequence of dice rolls (with replacement) using dice from $ F_k $, such that the sample space can be partitioned into $ N_k $ equally probable outcomes.
Equivalently:
Let $ S $ be the multiplicative semigroup generated by $ \{f_{k,1}, f_{k,2}, \dots, f_{k,K_k}\} $.
Then output 'Y' if $ N_k $ divides some element of $ S $; otherwise output 'N'.
That is:
$$
\exists m \in \mathbb{Z}^+, \exists e_1, \dots, e_{K_k} \in \mathbb{N} \text{ such that } N_k \mid \prod_{i=1}^{K_k} f_{k,i}^{e_i}
$$