High School Programming League Problems Archive

You are given X, a set of n < 20 positive integers: x₁, x₂, ... x_n, where x_i < 20. Let S=x₁ + x₂ + ... + x_n be the sum of all x_i. Please, check if there exists a subset of X whose sum of elements is equal to S/2.

Input

First t < 500, the nuber of sets. Next, for each test case, two lines follow. The first contains n, while the second the n set elements, separated by spaces.

Output

For each test case output one word in a separate line: YES if it is possible to achieve S/2 and NO if it is impossible.

Example

Input:
4
3
2 1 3
3
11 10 9
4 
1 2 1 6
5
11 1 2 10 18

Output:
YES
NO
NO
YES

Comment:
1: 2 + 1 = 3
2: no solution
3: no solution
4: 11 + 10 = 1 + 2 + 18

Scoring

By solving this problem you score 10 points.