CF1183F.Topforces Strikes Back

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.

一场重要的编程竞赛即将在最著名的编程平台（Topforces）上举行！

出题人手头有 $n$ 道题目，需要从中至多选出三道组成本次比赛。第 $i$ 道题的“美观度”为 $a_i$。出题人需构造出美观度总和最大的比赛（即所选题目的美观度之和尽可能大）。

但在比赛准备过程中有一个重要限制：由于出题人的一些迷信，所选题目的美观度之间不能存在整除关系。换言之，若所选题目的美观度为 $x, y, z$，则 $x$ 不能被 $y$ 或 $z$ 整除，$y$ 不能被 $x$ 或 $z$ 整除，且 $z$ 不能被 $x$ 或 $y$ 整除；若只选两道题，美观度为 $x$ 和 $y$，则 $x$ 不能被 $y$ 整除，且 $y$ 不能被 $x$ 整除；仅由一道题构成的比赛总是合法的。

你的任务是：对于给定的题目池，求出至多选三道题所能组成的比赛的最大总美观度。

你需要回答 $q$ 个相互独立的询问。

如果你使用 Python 编程，在提交代码时请考虑使用 PyPy 而非 Python。

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$.

输入的第一行包含一个整数 $q$（$1 \le q \le 2 \cdot 10^5$），表示查询次数。

每次查询的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示问题的数量。

每次查询的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$2 \le a_i \le 2 \cdot 10^5$），其中 $a_i$ 表示第 $i$ 个问题的美观度。

保证所有查询的 $n$ 值之和不超过 $2 \cdot 10^5$。

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.

对于每个查询，输出一个整数——从该查询给定的题目池中至多选出三道题目所组成的比赛的最大可能累计美观度。