原题链接：

You are given an array aa of length nn. The array is called 3SUM-closed if for all distinct indices ii, jj, kk, the sum ai+aj+akai+aj+ak is an element of the array. More formally, aa is 3SUM-closed if for all integers 1≤i<j<k≤n1≤i<j<k≤n, there exists some integer 1≤l≤n1≤l≤n such that ai+aj+ak=alai+aj+ak=al.

Determine if aa is 3SUM-closed.

Input

The first line contains an integer tt (1≤t≤10001≤t≤1000) — the number of test cases.

The first line of each test case contains an integer nn (3≤n≤2⋅1053≤n≤2⋅105) — the length of the array.

The second line of each test case contains nn integers a1,a2,…,ana1,a2,…,an (−109≤ai≤109−109≤ai≤109) — the elements of the array.

It is guaranteed that the sum of nn across all test cases does not exceed 2⋅1052⋅105.

Output

For each test case, output "YES" (without quotes) if aa is 3SUM-closed and "NO" (without quotes) otherwise.

You can output "YES" and "NO" in any case (for example, strings "yEs", "yes" and "Yes" will be recognized as a positive response).

Example

input

Copy

4
3
-1 0 1
5
1 -2 -2 1 -3
6
0 0 0 0 0 0
4
-1 2 -3 4

output

Copy

YES
NO
YES
NO

Note

In the first test case, there is only one triple where i=1i=1, j=2j=2, k=3k=3. In this case, a1+a2+a3=0a1+a2+a3=0, which is an element of the array (a2=0a2=0), so the array is 3SUM-closed.

In the second test case, a1+a4+a5=−1a1+a4+a5=−1, which is not an element of the array. Therefore, the array is not 3SUM-closed.

In the third test case, ai+aj+ak=0ai+aj+ak=0 for all distinct ii, jj, kk, and 00 is an element of the array, so the array is 3SUM-closed.

思路：

1，看数据范围，暴力过不去

2，如果正的多于2个，和一定大于任何2个，如果负的多于2个，和一定小于任何两个，0最多有2个，多了没有用。分类讨论。

3，暴力剩下的数，复杂度O(n+6^4)；

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxj=2e5+100;
int a[maxj];
void solve(){
    int n;
    cin>>n;
    vector<int>x,y,z;
    map<int,int>mp;
    for(int i=1;i<=n;++i){
        cin>>a[i];
        if(a[i]>0)x.emplace_back(a[i]);
        else if(a[i]<0)y.emplace_back(a[i]);
        else if(z.size()<2)z.emplace_back(a[i]);
        mp[a[i]]=1;
    }if(x.size()>2||y.size()>2){
        cout<<"NO"<<'\n';
        return ;
    }
    for(auto i:x)z.emplace_back(i);
    for(auto i:y)z.emplace_back(i);
    for(int i=0;i<z.size();++i){
        for(int j=i+1;j<z.size();++j){
            for(int k=j+1;k<z.size();++k){
                int x=z[i]+z[j]+z[k];
                if(!mp[x]){
                    cout<<"NO"<<'\n';
                    return ;
                }
            }
        }
    }cout<<"YES"<<'\n';
}    
int32_t main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);//ios与其他加速方式不可混用
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}