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.
//basic template
#include <bits/stdc++.h> 
#include <ext/pb_ds/assoc_container.hpp>
using namespace std; 
using namespace __gnu_pbds;
#define ll long long
const ll mod = 1e9+7;
const ll mod2= 998244353;
const ll INF = 1ll<<62;
const long double pi=3.1415926535897932384626433832795;
#define fo(i,n) for(ll i=0;i<(ll)n;++i)
#define fos(j,i,n) for(ll j=i;j<(ll)n;++j)
#define all(v) v.begin(),v.end()
/* #define endl "\n" */
#define dis(k) cout << k << endl
#define ret(k) { dis(k); return;}
#define ror(i,n) for(ll i=(ll)n-1;i>=0;--i)
#define ve vector
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define pf pop_front
#define ft front
#define bk back
#define puf push_front
#define setz(a) memset(a,0,sizeof(a))
#define seti(a) memset(a,0x7f,sizeof(a))
#define setmi(a) memset(a,0xc0,sizeof(a))
typedef ve< ll > vi;
typedef ve< vi > vvi;
typedef pair< ll ,ll > ii;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> indset;

//weird debugging stuff
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
	enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
		sim > struct rge { c b, e; };
		sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
		sim > auto dud(c* x) -> decltype(cerr << *x, 0);
		sim > char dud(...);
		struct debug {
#ifdef LOCAL
			~debug() { cerr << endl; }
			eni(!=) cerr << boolalpha << i; ris; }
		eni(==) ris << range(begin(i), end(i)); }
		sim, class b dor(pair < b, c > d) {
			ris << "(" << d.first << ", " << d.second << ")";
		}
sim dor(rge<c> d) {
	*this << "[";
	for (auto it = d.b; it != d.e; ++it)
		*this << ", " + 2 * (it == d.b) << *it;
	ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define im(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
const ll mxn=1e5+5;
ll f;
void rec(ll c,ll i,vi b,ll e,ll s,ll n){
	s+=c*b[i];
	if(i==n-1){
		if(s==e){
			dis("YES");
			f=1;
		}
		return;
	}
	if(f==1) return;
	rec(0,i+1,b,e,s,n);
	rec(-1,i+1,b,e,s,n);
	rec(1,i+1,b,e,s,n);
}


void akirametai(){
	ll n;
	cin >> n;
	ll a[n];
	fo(i,n) cin >> a[i];
	if(n==1){
		if(a[0]==0) ret("YES");
		ret("NO");
	}
	fo(i,n){
		ll s=0;
		vi b;
		f=0;
		fo(j,n) if(j!=i) b.pb(a[j]);
		rec(0,0,b,a[i],s,n-1);
		if(f==1) break;
		rec(-1,0,b,a[i],s,n-1);
		if(f==1) break;
		rec(1,0,b,a[i],s,n-1);
		if(f==1) break;
	}
	if(!f)dis("NO");
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t=1;
	cin >> t;		
	while(t--)
		akirametai();
}
