C. Divide it all again
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

As usual, as always, once again, Alice and Bob play a game with an array of integers. Both of them have a score of $$$0$$$ at the start of the game.

They start with an array $$$A$$$ of $$$n$$$ positive integers and play in turns. In each turn, the player must:

  • Choose an element $$$x$$$ present in the current array.
  • Choose an integer $$$k ~ \mathbf{(2 \leq k \leq 5)}$$$ such that $$$ x \bmod k = 0 $$$ ($$$k$$$ divides $$$x$$$). If no such $$$k$$$ exists, then the element $$$x$$$ is removed from the array and the player's score increases by 1.
  • If a valid $$$k$$$ is chosen, then the number $$$x$$$ is removed from the array and is then repeatedly divided by $$$k$$$ until it is not possible to divide by $$$k$$$. The value that remains is inserted back into the array.

    Equivalently, let $$$$$$x = t \cdot k^{p}$$$$$$ where $$$p \ge 1$$$ is the largest integer such that $$$k^{p}$$$ divides $$$x$$$, and $$$t \bmod k \neq 0$$$. Then, the original $$$x$$$ is removed from the array and the number $$$t$$$ is added back to the array.

The game ends when the array becomes empty. The winner is the player with the lower score at the end. If the scores are equal, the game is considered a tie.

Alice goes first. Given the initial array $$$A$$$, determine whether Alice wins the game or not, if both the players play optimally.

Input

The first line of each test contains a single integer $$$t ~ (1 \leq t \leq 10^3 )$$$ — the number of test cases.

The first line of each test case contains a positive integer $$$n ~ (1 \leq n \leq 2 \cdot 10^5)$$$ — the number of elements in the array $$$A$$$.

The second line of each test case contains $$$n$$$ positive integers $$$a_1 , a_2 , ... , a_n ~ (1 \leq a_i \leq 10^9)$$$ — denoting the array elements.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$

Output

For each test case, output a single line containing the word "YES" — if Alice wins the game and "NO" — otherwise.

Example
Input
4
1
8
4
13 26 39 52
3
70 30 70
2
10 20
Output
YES
NO
YES
NO
Note

For the first test case, the game proceeds as follows:

  • Initially $$$A= [8]$$$. Alice has to choose $$$x = 8$$$. Then, Alice chooses $$$k = 2$$$. After repeatedly dividing $$$x = 8$$$ with $$$k = 2$$$ , we get $$$8 \rightarrow 4 \rightarrow 2 \rightarrow 1$$$. Therefore, the array $$$A$$$ becomes $$$[1]$$$ .
  • Now, Bob has to choose $$$x = 1$$$. For this $$$x$$$ , since Bob cannot choose a $$$k ~(2 \leq k \leq 5)$$$ such that $$$x \bmod k = 0$$$, therefore $$$x$$$ is removed from the $$$A$$$ , and Bob's score is increased by $$$1$$$.
  • The array $$$A$$$ is empty and therefore the game ends. Since Alice has the lower score, therefore she wins and the answer is "YES".

For the second test case, a possible game proceeds as follows:

  • Initially $$$A = [13 , 26 , 39 , 52]$$$ . Alice chooses $$$x = 52$$$ and $$$k = 4$$$. After the repeated division, we get $$$52 \rightarrow 13$$$. Therefore, the array $$$A$$$ becomes $$$[13 , 26 , 39 , 13]$$$.
  • Now, Bob chooses $$$x = 26$$$ and $$$k = 2$$$. The array then becomes $$$[13 , 13 , 39 , 13]$$$.
  • Alice chooses $$$x = 39$$$ and $$$k = 3$$$. The array then becomes $$$[13 , 13 , 13 , 13]$$$.
  • Bob chooses $$$x = 13$$$ . Since there is no valid $$$k$$$, therefore his score gets increased by $$$1$$$. The array then becomes $$$[13 , 13 , 13]$$$.
  • Alice chooses $$$x = 13$$$ . Again, there is no valid $$$k$$$ and her score increases by $$$1$$$. The array becomes $$$[13 , 13]$$$ .
  • Bob chooses $$$x = 13$$$ . Again there is no valid $$$k$$$, and his score gets increased by $$$1$$$. The array then becomes $$$[13]$$$.
  • Alice chooses $$$x = 13$$$ . Again, there is no valid $$$k$$$ and her score increases by $$$1$$$.
  • Since the array becomes empty, and both of them have their scores equal to $$$2$$$, therefore the game is tied and the answer is "NO".