URI Online Judge | 1885

Thai Lotery

By Arthur Nascimento, Universidade de São Paulo BR Brazil

Timelimit: 1

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 input is composed of many instances. The first line of the input contains an integer T which indicates the number of instances.

Each instance is composed by 2 lines. The first one contains 2 integers, N (1 ≤ N ≤ 1018) and K (0 ≤ K ≤ 105), that represent the number of persons and the number of dice, respectively. The second line contains K integers. The i-th integer, say fi (1 ≤ fi ≤ 1018), represents the number of faces of the i-th die.


For each instance, print a single line containing a single character. Print 'Y' if its possible to do the lotery; otherwise, print 'N'.

Input Sample Output Sample

18 1
10 2
4 6
1 0