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 \(p^a\), if you are performing division by \(p^a\). 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 \le T \le 20\)
\( 1 \le N \le 10000\)
\( 1 \le S_i \le 10^6\)