One important contest will take place on the most famous programming platform (Topforces) very soon!
The authors have a pool of n problems and should choose at most three of them into this contest. The prettiness of the i-th problem is ai. The authors have to compose the most pretty contest (in other words, the cumulative prettinesses of chosen problems should be maximum possible).
But there is one important thing in the contest preparation: because of some superstitions of authors, the prettinesses of problems cannot divide each other. In other words, if the prettinesses of chosen problems are x,y,z, then x should be divisible by neither y, nor z, y should be divisible by neither x, nor z and z should be divisible by neither x, nor y. If the prettinesses of chosen problems are x and y then neither x should be divisible by y nor y should be divisible by x. Any contest composed from one problem is considered good.
Your task is to find out the maximum possible total prettiness of the contest composed of at most three problems from the given pool.
You have to answer q independent queries.
If you are Python programmer, consider using PyPy instead of Python when you submit your code.
Input
The first line of the input contains one integer q (1≤q≤2⋅105) — the number of queries.
The first line of the query contains one integer n (1≤n≤2⋅105) — the number of problems.
The second line of the query contains n integers a1,a2,…,an (2≤ai≤2⋅105), where ai is the prettiness of the i-th problem.
It is guaranteed that the sum of n over all queries does not exceed 2⋅105.
Output
For each query print one integer — the maximum possible cumulative prettiness of the contest composed of at most three problems from the given pool of problems in the query.
Example
Input
3
4
5 6 15 30
4
10 6 30 15
3
3 4 6
Output
30
31
10

题意：有n个互不相同的整数，现在至多选3个数，选出的数须两两不能相互整除，现在使这至多3个数的和最大，求这个和。
贪心。
（1）如果只选1个数，显然最大数最优
（2）选2个数，则选择最大的数和另外1个最大的合法的数
证明：1.选了两个不是最大数因数的数，那么用最大数替换其中一个肯定更优；
2.选了1个最大数因数和其他数，用最大数替换因数；
3。选了两个最大数x的因数，这俩数加起来最大为x/2+x/3<x，所以用最大数替换这两个数，然后另选1个最大的合法的数。
（3）选3个数，类比着（2）去分析情况：
1.3个不是最大数因数的数，用最大数替换
2.2个不是 1个是，用最大数替换是的那个
3.1个不是 2个是，同理（2），用最大数替换两个是的，然后再选1个
4.三个都是 这3个数加起来最大为x/2+x/3+x/5>x，次大为x/2+x/3+x/7<x;
所以选3个数时，先选最大数，然后依次选两个最大的合法的数，求和记为s，然后判断场上是否有最大值x的因数x/2,x/3,x/5,如果都有，那么ans=max(s,x/2,x/3,x/5)；否则ans=s.

#include<bits/stdc++.h>
using namespace std;
long long q,n;
long long a[200010];
long long vis[200010];
queue<long long> cnt;
long long maxmy(long long a,long long b)
{
    return a>b?a:b;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>q;
    long long ans;
    while(q--)
    {
        cin>>n;
        for(long long i=1;i<=n;++i)
        {
            cin>>a[i];
            vis[a[i]]=1;
            cnt.push(a[i]);
        }
        sort(a+1,a+1+n);

        ans=0;
        long long temp=0;
        for(int i=n-1;i;--i)
        {
            if(a[n]%a[i]==0)
            {
                if(a[n]==2*a[i]) ++temp;
                if(a[n]==3*a[i]) ++temp;
                if(a[n]==5*a[i]) ++temp;
            }
        }

        long long t=0;
        for(int i=n;i;--i)
        {
            if(vis[a[i]])
            {
                for(int j=i-1;j;--j)
                {
                    if(a[i]%a[j]==0)
                    { 
                        vis[a[j]]=0;
                    }
                }
                ans+=a[i];
                ++t;
            }
            if(t>=3) break;
        }

        if(temp>=3)ans=maxmy(ans,a[n]/30*31);

        cout<<ans<<endl;
        while(!cnt.empty())
        {
            vis[cnt.front()]=0;
            cnt.pop();
        }
    }
    return 0;
}