Algorithm

B. 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 (1t1041≤�≤104) — the number of test cases. Then t test cases follow.

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

The next line contains n integers a1,a2,,an�1,�2,…,�� — the weights of the candies. The weight of each candy is either 11 or 22.

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

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 yEsyesYes and YES will be recognized as positive).

Example
input
Copy
5
2
1 1
2
1 2
4
1 2 1 2
3
2 2 2
3
2 1 2

output
Copy
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 11.

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 22.

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.

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include<bits/stdc++.h>
using namespace std;

int main(){
int t;
cin>>t;
int n, x;
while(t--){
cin>>n;
int count1 = 0, count2 = 0;
for(int i = 0; i < n; i++){
cin>>x;
if(x == 1){
count1++;
continue;
}
count2++;
}
if(count2 % 2 == 0 && count1 % 2 == 0){
cout<<"YES"<<endl;
continue;
}
if(count2 % 2 != 0 && count1 % 2 == 0 && count1 > 0){
cout<<"YES"<<endl;
continue;
}
cout<<"NO"<<endl;
}
return 0;
}
Copy The Code &

Input

cmd
5
2
1 1
2
1 2
4
1 2 1 2
3
2 2 2
3
2 1 2

Output

cmd
YES
NO
YES
NO
NO