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.
import java.io.IOException;
import java.io.InputStream;
import java.util.*;


public class Main {
	static int val[];
	static boolean arr[];
	static int f, n;
	static void recurse(int i, boolean gen[]){
		if(i==n){
			int sum=0, count=0, s=0;;
			for(int j=0;j<n;j++){
				if(gen[j]){
					count++;
					sum+=val[j];
				}
				if(j<n/2){
					if(gen[j] && gen[j+n/2]){
						s=1;
					}
				}
			}
			if(sum<0){
				sum= sum*-1;
			}
			if(sum<=100000 && count>1 && arr[sum] && s==0){
				f=1;
			}
			return;
		}
		if(f==1)
			return;
		recurse(i+1, gen);
		gen[i]=true;
		recurse(i+1, gen);
		gen[i]=false;
	}
    public static void main(String[] args)throws IOException {
        FastReader in=new FastReader(System.in);
        int t=in.nextInt();
        StringBuilder sb=new StringBuilder();
        int i,j,k,tc=0;
        while(t-->0){
			n = in.nextInt();
		    arr= new boolean[100001];
			val= new int[2*n];
			f=0;
			for(i=0;i<n;i++){
				int x=in.nextInt();
				if(x<0)
					x= x*-1;
				val[i]=x;
				if(arr[x] || x ==0){
					f=1;
				}
				arr[x]=true;
			}

			if(f==1){
				sb.append("YES\n");
				continue;
			}
			for(i=0;i<n;i++){
				val[i+n] = val[i]*-1;
			}

			n=2*n;
			recurse(0, new boolean[n]);

			if(f==1)
				sb.append("YES\n");
			else
				sb.append("NO\n");

			

			
			
			
			
		}

		System.out.print(sb);
    }
}

class Node {
    int setroot, dist;
    public Node(int setroot, int dist){
        this.setroot = setroot;
        this.dist = dist;
    }
    @Override
    public String toString() {
        return String.format(setroot + ", " + dist);
    }
}

class FastReader {

    byte[] buf = new byte[2048];
    int index, total;
    InputStream in;

    FastReader(InputStream is) {
        in = is;
    }

    int scan() throws IOException {
        if (index >= total) {
            index = 0;
            total = in.read(buf);
            if (total <= 0) {
                return -1;
            }
        }
        return buf[index++];
    }

    String next() throws IOException {
        int c;
        for (c = scan(); c <= 32; c = scan()) ;
        StringBuilder sb = new StringBuilder();
        for (; c > 32; c = scan()) {
            sb.append((char) c);
        }
        return sb.toString();
    }

    int nextInt() throws IOException {
        int c, val = 0;
        for (c = scan(); c <= 32; c = scan()) ;
        boolean neg = c == '-';
        if (c == '-' || c == '+') {
            c = scan();
        }
        for (; c >= '0' && c <= '9'; c = scan()) {
            val = (val << 3) + (val << 1) + (c & 15);
        }
        return neg ? -val : val;
    }

    long nextLong() throws IOException {
        int c;
        long val = 0;
        for (c = scan(); c <= 32; c = scan()) ;
        boolean neg = c == '-';
        if (c == '-' || c == '+') {
            c = scan();
        }
        for (; c >= '0' && c <= '9'; c = scan()) {
            val = (val << 3) + (val << 1) + (c & 15);
        }
        return neg ? -val : val;
    }
}
