I. Number Game
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There is a sequence of length $$$n$$$, and the weight of the $$$i$$$-th number is $$$a_i$$$. Two players, A and B, are playing a game, taking turns to operate on the sequence. Each player has two options to choose from:

  • Remove any two numbers $$$a_i,a_j$$$ ($$$i \neq j$$$) from the sequence, and add a number with weight $$$a_i+a_j$$$ to the sequence. This operation cannot be performed when there is only one number in the sequence.
  • Take a number from the sequence, and the remaining numbers in the sequence will have their weights added together and given to the other player, ending the game.

If the final total weight obtained by A is greater, then A wins; otherwise, B wins.

A goes first to make a move. Determine if A has a winning strategy. It is guaranteed that the sum of $$$a_i$$$ is odd.

Input

This problem contains multiple test cases.

The first line contains an integer $$$T$$$ ($$$1\leq T\leq 10^5$$$), indicating the number of test cases.

For each test case, the input format is as follows.

The first line contains an integer $$$n$$$ ($$$1\leq n\leq 5 \times 10^5$$$), indicating the initial length of the sequence.

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1\leq a_i\leq 10^9$$$), representing the initial sequence.

It is guaranteed that $$$\sum n\leq 10^6$$$ and $$$\sum a_i$$$ is odd.

Output

For each test case, if A has a winning strategy, output YES; otherwise, output NO.

Example
Input
3
3
3 6 4
2
1 2
3
2 5 6
Output
NO
YES
NO
Note

Explanation for Example 1:

  • If A chooses the weight $$$3$$$, then B can obtain a weight of $$$6+4=10$$$.
  • If A chooses the weight $$$4$$$, then B can obtain a weight of $$$3+6=9$$$.
  • If A chooses the weight $$$6$$$, then B can obtain a weight of $$$3+4=7$$$.
  • If A chooses to merge the weights $$$3,6$$$, the sequence becomes $$$9,4$$$. If B chooses the weight $$$9$$$, then A can obtain a weight of $$$4$$$.
  • If A chooses to merge the weights $$$3,4$$$, the sequence becomes $$$7,6$$$. If B chooses the weight $$$7$$$, then A can obtain a weight of $$$6$$$.
  • If A chooses to merge the weights $$$4,6$$$, the sequence becomes $$$10,3$$$. If B chooses the weight $$$10$$$, then A can obtain a weight of $$$3$$$.

In all cases, B can obtain a higher weight with the optimal strategy, so A cannot win.

Explanation for Example 2:

If A chooses the weight $$$2$$$, then B can obtain a weight of $$$1$$$.

Therefore, A has a winning strategy.