H. Game with wife
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Besher and his wife are playing a game on $$$n$$$ piles of stones, each one contains $$$a_i$$$ stones. On each player's turn, they can do one of these actions:

  • choose $$$1$$$ non-empty pile and take $$$1$$$ stone from it.
  • choose $$$3$$$ non-empty piles of same parity of numbers of stones and take $$$1$$$ stone from each of them.

The first player who is unable to make a move loses (all piles are empty).

Given that Besher goes first, who will win the game if both players play optimally?

Input

Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ $$$(1 \le t \le 10^4)$$$ — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ $$$(1 \leq n \leq 2 \cdot 10^{5})$$$ — the number of piles in the game.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \le a_i \le 10^9)$$$ — the elements of the array $$$a$$$, describing the initial number of stones.

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 "YES" if Besher wins, and output "NO" otherwise.

Example
Input
3
3
1 2 3
2
1 2
1
1
Output
NO
YES
YES