Topforces Strikes Back
Contest: Codeforces Round 570 (Div. 3)
Difficulty rating: 2100
Tags: brute force, math, sortings

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 $$$a_i$$$. 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 format:
The first line of the input contains one integer $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$) — the number of queries.

The first line of the query contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of problems.

The second line of the query contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$2 \le a_i \le 2 \cdot 10^5$$$), where $$$a_i$$$ is the prettiness of the $$$i$$$-th problem.

It is guaranteed that the sum of $$$n$$$ over all queries does not exceed $$$2 \cdot 10^5$$$.

Output format:
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.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Example input:
3
4
5 6 15 30
4
10 6 30 15
3
3 4 6

Example output:
30
31
10

Editorial:
I know about some solutions that are trying to iterate over almost all possible triples, but I have a better and more interesting one. Possibly, it was already mentioned in comments, but I need to explain it.
Let's solve the problem greedily. Let's sort the initial array. The first number we would like to choose is the maximum element. Then we need to pop out some maximum elements that are divisors of the maximum. Then there are two cases: the array becomes empty, or we have some maximum number that does not divide the chosen number. Let's take it and repeat the same procedure again, but now we have to find the number that does not divide neither the first taken number nor the second taken number.
So we have at most three numbers after this procedure. Let's update the answer with their sum. This solution is almost correct. Almost! What have we forgotten? Let's imagine that the maximum element is divisible by $$$2$$$, $$$3$$$ and $$$5$$$ and there are three following numbers in the array: maximum divided by $$$2$$$, by $$$3$$$ and by $$$5$$$. Then their sum is greater than the maximum (and may be greater than the answer we have!) because $$$\frac{1}{2} + \frac{1}{3} + \frac{1}{5} > 1$$$. So if these conditions are satisfied, let's update the answer with the sum of these three numbers.
It can be shown that this is the only possible triple that can break our solution. The triple $$$2, 3, 4$$$ does not match because the maximum divided by $$$4$$$ divides the maximum divided by $$$2$$$. The triple $$$2, 3, 6$$$ is bad for the same reason. And the triple $$$2, 3, 7$$$ has sum less than the maximum element.