403151: GYM101047 G Thai Lottery

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:

• several dice may be rolled at the same round;
• previous rounds may affect the choice of dice in the next rounds;
• the same die can be rolled in multiple rounds.

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 f_i is the number of faces in the i-th die.

Limits

• 1 ≤ T ≤ 120
• 1 ≤ N ≤ 10¹⁸
• 0 ≤ K ≤ 10⁵
• The sum of K over all test cases will not exceed 6·10⁵
• 1 ≤ f_i ≤ 10¹⁸

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.

3
18 1
6
1 0

10 2
4 6

Y
Y
N