Wire Connection

Time limit2sMemory limit128 MB

Summary

Decide whether a subset of given semicircular wires can be joined end to end, with free rotation at joints, to form one closed non-overlapping loop.

Level: Medium7 of 10
Topics: Geometry, Dynamic programming, Math
Solved: No attempts yet

Problem

There are N semicircular wires. For each wire, its radius is given.

You may choose some of the wires and attach endpoints of two wires at any angle, rotating each semicircle freely. Determine whether the chosen wires can be connected by endpoints to form one connected closed curve. The middle parts of different wires must not overlap.

Input

The first line contains the number of data sets K (1 <= K <= 30).

For each data set, the first line contains N (1 <= N <= 20). The next line contains N real numbers, the radii of the semicircles. Each radius is a positive real number at most 10,000,000 and may be given with up to three digits after the decimal point.

Output

For each data set, print YES if it is possible, and NO otherwise.

Examples1

Example 1

Input

4
1
4.000
2
1.000 1.000
3
1.455 2.958 4.424
7
1.230 2.577 3.411 2.968 5.301 4.398 6.777

Expected output

NO
YES
NO
YES