Bond

Time limit1sMemory limit128 MB

Summary

Decide for each test case whether some connected loopless multigraph has exactly the given valencies as degrees.

Level: Medium7 of 10
Topics: Graph, Math
Solved: No attempts yet

Problem

Tom is a chemist who is interested in molecular structure. He recently discovered a new kind of atom and named it a tomatom. When two or more tomatoms are joined by bonds they form a molecule called a tomolecule. In chemistry, the valency of an atom is the number of bonds that join it to its neighbors. The tomatoms in a tomolecule are joined so that all of the following hold:

Every tomatom is joined by at least one bond, and there may be more than one bond between the same pair of tomatoms.
The tomolecule is connected: between every two tomatoms there is a path made of bonds, so there are no isolated pieces.
No tomatom is bonded to itself.

Tom wants to study the valencies in a tomolecule. Given a list of positive integers, he wants to know whether some tomolecule can have exactly those integers as the valencies of its tomatoms while satisfying the three conditions above.

For example, suppose three tomatoms have target valencies 50, 60, and 70; call them $A_1$ , $A_2$ , and $A_3$ . If there are 20 bonds between $A_1$ and $A_2$ , 30 bonds between $A_1$ and $A_3$ , and 40 bonds between $A_2$ and $A_3$ , then the valencies of $A_1$ , $A_2$ , $A_3$ are 50, 60, 70, so a matching tomolecule exists. For the integers 10, 20, 40 no such tomolecule exists. For four tomatoms with valencies 1, 1, 1, 1 there is also no tomolecule, because condition (2) cannot be satisfied.

Write a program that, given the positive integers, decides whether a tomolecule whose tomatom valencies are exactly those integers, and that satisfies the conditions above, can exist.

Input

The input is read from standard input. The first line contains the number of test cases $T$ . Each test case is given on two lines. The first line contains an integer $N$ , the number of tomatoms, with $2 \le N \le 200$ . The second line contains $N$ nondecreasing positive integers; the $k$ -th of them is the valency of tomatom $A_k$ (for $1 \le k \le N$ ). The integers are separated by single spaces, and each integer is between 1 and 10000, inclusive.

Output

The output is written to standard output. For each test case, print a single line containing YES if some tomolecule can have exactly the given integers as the valencies of its tomatoms while satisfying all three conditions, and NO otherwise.

Examples2

Example 1

Input

5
3
50 60 70
3
10 20 40
4
1 1 1 1
6
1 1 1 1 1 5
6
1 1 1 1 4 4

Expected output

YES
NO
NO
YES
YES

Example 2
Input
```
3
2
5 5
2
3 4
2
1 1
```
Expected output
```
YES
NO
YES
```