Mancunian and his arch-enemy Liverbird are playing a game. They have a multiset of positive integers available and they alternate turns. Mancunian always starts.
Each move consists of choosing some prime number p and then choosing a non-empty subset of the multiset such that each element of the subset is divisible by p. Then, the player divides each member of the subset by some non-zero power of p.
Note that the element must be divisible by pa, if you are performing division by pa. For example, if the chosen prime is 3, then 18 is divisible by 9 but not by 27. Also, it is not necessary to divide each element of the subset with the same power of p.
Input:
The first line contains a single integer T denoting the number of test cases.
The first line of each test case contains a single integer N denoting the number of elements in the multiset S.
The second line of each test case contains N integers denoting the elements of the multiset.
Output:
For each test case, print the name of the winning player in a new line.
Constraints:
1≤T≤20
1≤N≤10000
1≤Si≤106
Consider the first case. In the first move, Mancunian chooses one prime from the set {2, 3, 5}. If he chooses 2, then he has to choose the subset containing only the value 2 from the array and divide it by 2. In the next move, Liverbird chooses one of the primes {3, 5}. If he chooses 3, then he has to choose the subset containing only the value 3 from the array and divide it by 3. In the last move, Mancunian repeats the same with the prime 5. Liverbird cannot make a move and he loses. All other possible paths of the game are analogous to this one.
