Little E and Little W are playing a game called "E&D". The rules of the game are as follows:

There are $2n$ piles of stones on the table, numbered $1 \dots 2n$. For convenience, we consider the $(2k-1)$-th pile and the $2k$-th pile ($1 \le k \le n$) as a single group. The number of stones in the $i$-th pile is represented by a positive integer $S_i$.

A split operation consists of choosing any pile of stones on the table and removing it. Then, one splits the other pile in the same group by taking some stones from it and placing them in the position where the first pile was removed, forming a new pile. After the operation is completed, the number of stones in all piles must be greater than $0$. Obviously, the number of stones in the pile being split must be at least $2$.

Two players take turns performing the split operation. If it is a player's turn and all piles contain exactly $1$ stone, there are no stones left to operate on, and that player loses the game. Little E performs the first split. He wants to know if there exists a strategy that guarantees he will defeat Little W. Therefore, he turns to Little F, which is you, to tell him whether a winning strategy exists.

For example, suppose there are initially $4$ piles of stones on the table with quantities $1, 2, 3, 1$. Little E can choose to remove the $1$st pile and then split the $2$nd pile (only $1$ stone can be split off). Next, Little W can only choose to remove the $4$th pile and then split the $3$rd pile into $1$ and $2$. Finally, it is Little E's turn; he can only remove one of the piles with $1$ stone from the last two and split the other pile into $1$ and $1$. Thus, when it is Little W's turn, all piles contain $1$ stone, so he loses the game. Therefore, Little E has a winning strategy.

Input

The first line contains a positive integer $T$ ($T \le 20$), representing the number of test cases. This is followed by $T$ sets of data.

For each set of data, the first line is a positive integer $N$, representing the total number of piles on the table. The input data guarantees that $N$ is an even number.

The second line contains $N$ positive integers $S_1 \dots S_N$, representing the number of stones in each pile.

Output

The output contains $T$ lines. For each test case, if Little E has a winning strategy, output "YES"; otherwise, output "NO".

Constraints

For $20\%$ of the data, $N = 2$; For another $20\%$ of the data, $N \le 4$, $S_i \le 50$; For $100\%$ of the data, $N \le 2 \times 10^4$, $S_i \le 2 \times 10^9$.

Examples

Input 1

2
4
1 2 3 1
6
1 1 1 1 1 1

Output 1

YES
NO