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.
                    /*
                    TO LEARN
            
                    2-euler tour
                
                    */
                    /*
                    TO SOLVE 
                    codeforces 722 kavi on pairing duty
                    */
                    /*
                    bit manipulation shit
                    1-Computer Systems: A Programmer's Perspective
                    2-hacker's delight
                    3-(02-03-bits-ints)
                    4-machine-basics
                    5-Bits Manipulation tutorialspoint
                    */
                    /*
                    TO WATCH
                    
                    */
                                import java.util.*;
                                import java.math.*;
                                import java.io.*; 
                                import java.util.stream.Collectors;

                                   public class B{
                                static FastScanner scan=new FastScanner();
                                 public static PrintWriter out = new PrintWriter (new BufferedOutputStream(System.out));            
                static long gcd(long x,long y)
                {
                    if(x==0)
                        return y;
                    return gcd(y%x,x);
                }
                static long lcm(long x,long y)
                {
                    return (x*y)/(gcd(x,y));
                }
                static BigInteger LCM(BigInteger f,BigInteger s)
                {
                    BigInteger gcd=GCD(f,s);
                    BigInteger multiply = f.multiply(s);
                    return multiply.divide(gcd);
                }
                static BigInteger ZERO = new BigInteger("0");
               static BigInteger GCD(BigInteger a, BigInteger b){
        if (b.equals(ZERO))
            return a;
        else
            return GCD(b, a.mod(b));
    }
     static long modInverse(long a, long m)
    {
        long m0 = m;
        long y = 0, x = 1;
 
        if (m == 1)
            return 0;
 
        while (a > 1) {
            // q is quotient
            long q = a / m;
 
            long t = m;
 
            // m is remainder now, process
            // same as Euclid's algo
            m = a % m;
            a = t;
            t = y;
 
            // Update x and y
            y = x - q * y;
            x = t;
        }
 
        // Make x positive
        if (x < 0)
            x += m0;
 
        return x;
    }
    static boolean brute(int i,int arr[],int res[])
    {
        if(i==arr.length+1)
        {
            int cur=0;
            boolean all=false;
            for(int l=0;l<arr.length;l++){
cur=0;
                         for(int j=0;j<=arr.length;j++)
                                        {
                                            for(int k=0;k<=arr.length;k++)
                                            {
                                                if(res[j]-res[k]==arr[l])
                                                    cur++;
                                            }
                                        }
                                        if(cur>1){
                                       //     out.println(Arrays.toString(res));
                                            all=true;
                                           // return true;
                                        }
                                        if(cur<=0)
                                            return false;
                                        //return false;
            }
            return all;
        }
        boolean is1=false,is2=false,is3=false;
        res[i]=res[i-1]+arr[i-1];
        is1=brute(i+1,arr,res);
        res[i]=res[i-1]-arr[i-1];
        is2=brute(i+1,arr,res);
        res[i]=arr[i-1];
        is2=brute(i+1,arr,res);
        return is1|is2;
    }
 
                public static void main(String[] args)  throws Exception 
                          {
                     

                        //      scan=new FastScanner("D:\\usaco test data\\W.txt");
                         // out = new PrintWriter("D:\\usaco test data\\WW.txt");
                             
                                                         /*
                             READING 
                        
                             3-Introduction to DP with Bitmasking codefoces
                             4-Bit Manipulation hackerearth
                             5-read more about mobious and inculsion-exclusion 
                             */
                             /*
                             if it has no Xs or Os then the answer is 0
                           
                             */
                            
                                int tt=1;
                              
              tt=scan.nextInt();
                int T=1;
                               //System.out.println(8|9);
              
                         outer:while(tt-->0)
                                {
                                    int n=scan.nextInt();
                                    int arr[]=new int[n];
                                    int res[]=new int[n+1];
                                    for(int i=0;i<n;i++)
                                        arr[i]=Math.abs(scan.nextInt());
                                    /*for(int i=1;i<=n;i++)
                                    {
                                        res[i]=res[i-1]+arr[i-1];
                                    }*/
                                    boolean is=brute(1,arr,res);
                                    if(is)
                                        out.println("YES");
                                    else out.println("NO");
                                    //out.println(Arrays.toString(res));
                                    /*for(int i=0;i<n;i++)
                                    {
                                        int cur=0;
                                        for(int j=0;j<=n;j++)
                                        {
                                            for(int k=0;k<=n;k++)
                                            {
                                                if(res[j]-res[k]==arr[i])
                                                    cur++;
                                            }
                                        }
                                        if(cur>1)
                                        {
                                            out.println("YES");
                                            continue outer;

                                        }
                                    }*/
                                   // out.println("NO");


                            
                                
                                
                            }

                            

    out.close();
                }
              
                                
                               
                                 static long binexp(long a,long n)
                                {
                                    if(n==0)
                                        return 1;
                                    long res=binexp(a,n/2);
                                    if(n%2==1)
                                        return res*res*a;
                                    else 
                                        return res*res;
                                }
                                 
                                static long powMod(long base, long exp, long mod) {
                                       if (base == 0 || base == 1) return base;
                                       if (exp == 0) return 1;
                                       if (exp == 1) return (base % mod+mod)%mod;
                                       long R = (powMod(base, exp/2, mod) % mod+mod)%mod;
                                       R *= R;
                                       R %= mod;
                                       if ((exp & 1) == 1) {
                                           return (base * R % mod+mod)%mod;
                                       }
                                       else return (R %mod+mod)%mod;
                                   }
                                static double dis(double x1,double y1,double x2,double y2)
                                {
                                    return Math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
                                }
                                static long mod(long x,long y)
                                    {
                                        if(x<0)
                                            x=x+(-x/y+1)*y;
                                        return x%y;
                                    }
                                 public static  long pow(long b, long e) {
                                            long r = 1;
                                            while (e > 0) {
                                                if (e % 2 == 1) r = r * b ;
                                                b = b * b;
                                                e >>= 1;
                                            }
                                            return r;
                                        }
                                private static void sort(long[] arr) {
                                        List<Long> list = new ArrayList<>();
                                        for (long object : arr) list.add(object);
                                        Collections.sort(list);
                                    //Collections.reverse(list);
                                        for (int i = 0; i < list.size(); ++i) arr[i] = list.get(i);
                                    }
                                private static void sort2(long[] arr) {
                                        List<Long> list = new ArrayList<>();
                                        for (Long object : arr) list.add(object);
                                        Collections.sort(list);
                                    Collections.reverse(list);
                                        for (int i = 0; i < list.size(); ++i) arr[i] = list.get(i);
                                    }
                                 static class FastScanner
                    {
                        private int BS = 1 << 16;
                        private char NC = (char) 0;
                        private byte[] buf = new byte[BS];
                        private int bId = 0, size = 0;
                        private char c = NC;
                        private double cnt = 1;
                        private BufferedInputStream in;
                     
                        public FastScanner() {
                            in = new BufferedInputStream(System.in, BS);
                        }
                     
                        public FastScanner(String s) {
                            try {
                                in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
                            } catch (Exception e) {
                                in = new BufferedInputStream(System.in, BS);
                            }
                        }
                     
                        private char getChar() {
                            while (bId == size) {
                                try {
                                    size = in.read(buf);
                                } catch (Exception e) {
                                    return NC;
                                }
                                if (size == -1) return NC;
                                bId = 0;
                            }
                            return (char) buf[bId++];
                        }
                     
                        public int nextInt() {
                            return (int) nextLong();
                        }
                     
                        public int[] nextInts(int N) {
                            int[] res = new int[N];
                            for (int i = 0; i < N; i++) {
                                res[i] = (int) nextLong();
                            }
                            return res;
                        }
                     
                        public long[] nextLongs(int N) {
                            long[] res = new long[N];
                            for (int i = 0; i < N; i++) {
                                res[i] = nextLong();
                            }
                            return res;
                        }
                     
                        public long nextLong() {
                            cnt = 1;
                            boolean neg = false;
                            if (c == NC) c = getChar();
                            for (; (c < '0' || c > '9'); c = getChar()) {
                                if (c == '-') neg = true;
                            }
                            long res = 0;
                            for (; c >= '0' && c <= '9'; c = getChar()) {
                                res = (res << 3) + (res << 1) + c - '0';
                                cnt *= 10;
                            }
                            return neg ? -res : res;
                        }
                     
                        public double nextDouble() {
                            double cur = nextLong();
                            return c != '.' ? cur : cur + nextLong() / cnt;
                        }
                     
                        public double[] nextDoubles(int N) {
                            double[] res = new double[N];
                            for (int i = 0; i < N; i++) {
                                res[i] = nextDouble();
                            }
                            return res;
                        }
                     
                        public String next() {
                            StringBuilder res = new StringBuilder();
                            while (c <= 32) c = getChar();
                            while (c > 32) {
                                res.append(c);
                                c = getChar();
                            }
                            return res.toString();
                        }
                     
                        public String nextLine() {
                            StringBuilder res = new StringBuilder();
                            while (c <= 32) c = getChar();
                            while (c != '\n') {
                                res.append(c);
                                c = getChar();
                            }
                            return res.toString();
                        }
                     
                        public boolean hasNext() {
                            if (c > 32) return true;
                            while (true) {
                                c = getChar();
                                if (c == NC) return false;
                                else if (c > 32) return true;
                            }
                        }
                    }

                                 static class Pair implements Comparable<Pair>{
                                        public long x, y,z;
                                        public Pair(long x1, long y1,long z1) {
                                            x=x1;
                                            y=y1;
                                            z=z1;
                                        }
                                         public Pair(long x1, long y1) {
                                            x=x1;
                                            y=y1;
                                
                                        }
                                        
                                        @Override
                                        public int hashCode() {
                                            return (int)(x + 31 * y);
                                        }
                                        public String toString() {
                                            return x + " " + y+" "+z;
                                        }
                                        @Override
                                        public boolean equals(Object o){
                                            if (o == this) return true;
                                            if (o.getClass() != getClass()) return false;
                                            Pair t = (Pair)o;
                                            return t.x == x && t.y == y&&t.z==z;
                                        }
                                public int compareTo(Pair o)
                                {
                                 
                              
                                    return (int)(z-o.z);
                                 
                                    }
                                 
                                }
                                
                                }

                                 
