human
You are given a sequence of n integers a_1,   a_2,   ...,   a_n.

Does there exist a sequence of n integers b_1,   b_2,   ...,   b_n such that the following property holds?

  * For each 1 ≤ i ≤ n, there exist two (not necessarily distinct) indices j and k (1 ≤ j,   k ≤ n) such that a_i = b_j - b_k. 

Input

The first line contains a single integer t (1 ≤ t ≤ 20) — the number of test cases. Then t test cases follow.

The first line of each test case contains one integer n (1 ≤ n ≤ 10).

The second line of each test case contains the n integers a_1,   ...,   a_n (-10^5 ≤ a_i ≤ 10^5).

Output

For each test case, output a line containing YES if a sequence b_1,   ...,   b_n satisfying the required property exists, and NO otherwise.

Example

Input

5
5
4 -7 -1 5 10
1
0
3
1 10 100
4
-3 2 10 2
9
25 -171 250 174 152 242 100 -205 -258

Output

YES
YES
NO
YES
YES

Note

In the first test case, the sequence b = [-9,   2,   1,   3,   -2] satisfies the property. Indeed, the following holds: 

  * a_1 = 4 = 2 - (-2) = b_2 - b_5.

  * a_2 = -7 = -9 - (-2) = b_1 - b_5.

  * a_3 = -1 = 1 - 2 = b_3 - b_2.

  * a_4 = 5 = 3 - (-2) = b_4 - b_5.

  * a_5 = 10 = 1 - (-9) = b_3 - b_1. 


In the second test case, it is sufficient to choose b = [0], since a_1 = 0 = 0 - 0 = b_1 - b_1.

In the third test case, it is possible to show that no sequence b of length 3 satisfies the property.
The above is tricky. Write me a correct solution in PYTHON3.
 Write me a the Python program you requested?
assistant
#Here is the Python program you requested.

import bisect
import heapq
import math
import collections
import sys
import copy
from functools import reduce
import decimal
from io import BytesIO, IOBase
import os
import itertools
import functools
from types import GeneratorType

sys.setrecursionlimit(10 ** 9)
decimal.getcontext().rounding = decimal.ROUND_HALF_UP

graphDict = collections.defaultdict

queue = collections.deque

################## pypy deep recursion handling ##############
# Author = @pajenegod
def bootstrap(f, stack=[]):
    def wrappedfunc(*args, **kwargs):
        to = f(*args, **kwargs)
        if stack:
            return to
        else:
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        return to
                    to = stack[-1].send(to)

    return wrappedfunc

################## Graphs ###################
class Graphs:
    def __init__(self):
        self.graph = graphDict(set)

    def add_edge(self, u, v):
        self.graph[u].add(v)
        self.graph[v].add(u)

    def dfs_utility(self, nodes, visited_nodes, psf):
        global ans
        if len(visited_nodes.keys()) == n:
            ans = psf
            return
        visited_nodes[nodes] = None
        for neighbour in self.graph[nodes]:
            if neighbour not in visited_nodes:
                self.dfs_utility(neighbour, visited_nodes, psf + [neighbour])
        visited_nodes.pop(nodes)
        return

    def dfs(self, node):
        global ans
        Visited = collections.OrderedDict()
        self.dfs_utility(node, Visited, [node])

    def bfs(self, node):
        visited = set()
        if node not in visited:
            queue.append(node)
            visited.add(node)
        while queue:
            parent = queue.popleft()
            print(parent)
            for item in self.graph[parent]:
                if item not in visited:
                   ...