Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

F. Topforces Strikes Back

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputOne 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

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

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

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/23/2020 02:16:27 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|