Build a Square from Sticks

Interview

Time limit1sMemory limit128 MB

Summary

Given up to 20 stick lengths, decide whether all sticks can be split into four groups of equal total length.

Level: Medium6 of 10
Topics: Backtracking, Recursion, Sorting, Brute force
Solved: No attempts yet

Problem

You are given $N$ sticks whose lengths may differ. Determine whether you can use all of the sticks to form the four sides of a square.

A stick cannot be cut, each stick must belong to exactly one side, and the four sides must have equal length. In other words, a square can be formed if and only if the sticks can be split into four groups whose length sums are all equal.

Input

The first line contains the number of test cases $T$ . Each test case is given on a single line. The first integer on that line is the number of sticks $N$ ( $4 \le N \le 20$ ). It is followed by $N$ space-separated integers giving the stick lengths, where each length is a natural number between $1$ and $10000$ inclusive.

Output

For each test case, print yes on its own line if all the sticks can be used to form a square, or no otherwise.

Examples1

Example 1

Input

3
4 1 1 1 1
5 10 20 30 40 50
8 1 7 2 6 4 4 3 5

Expected output

yes
no
yes