CF:Fair Division

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Alice and Bob received n  candies from their parents. Each candy weighs either 1 gram or 2 grams. Now they want to divide all candies among themselves fairly so that the total weight of Alice's candies is equal to the total weight of Bob's candies.

Check if they can do that.

Note that candies are not allowed to be cut in half.

Input

The first line contains one integer t(1≤t≤104) — the number of test cases. Then t test cases follow.

The first line of each test case contains an integer n (1≤n≤100) — the number of candies that Alice and Bob received.

The next line contains nintegers a1,a2,…,an — the weights of the candies. The weight of each candy is either 1or 2.

It is guaranteed that the sum of n over all test cases does not exceed 105.

Output

For each test case, output on a separate line:

• "YES", if all candies can be divided into two sets with the same weight;

• "NO" otherwise.

You can output "YES" and "NO" in any case (for example, the strings yEs, yes, Yes and YES will be recognized as positive).

Example

input

5 

2

1 1 

2

1 2

4

1 2 1 2

3

2 2 2

3

2 1 2

output

YES 

NO 

YES 

NO 

NO

Note

In the first test case, Alice and Bob can each take one candy, then both will have a total weight of 1.

In the second test case, any division will be unfair.

In the third test case, both Alice and Bob can take two candies, one of weight 11 and one of weight 2.

In the fourth test case, it is impossible to divide three identical candies between two people.

In the fifth test case, any division will also be unfair.

这里面说的是分糖果的问题，就是有2种糖果，1种对应的大小是1，另一种对应的是2，其中2的糖果不能分割，那么求出来如果按照这种给定的糖果数量，能不能将他们平均分配呢？

1：放到map中。1跟2分别对应的数量；

2：如果2*a+1*b是奇数，那么肯定不能分配；

3：如果是偶数，那么就要看a跟b的数字是否是偶数；

3.1a 跟b都是偶数，肯定可以；

3.2 a是奇数，b是偶数的话，也是可以的，但是b要大于等于2才行；

其他情况就不能平均分配了。

以上是思路，下面是代码：