Maximum Total Efficiency

You are given T test cases. For each test case, you are given an integer N representing the number of workers and a list of N positive integers that represent the efficiency of each worker.

You can split the workers into two groups. The first group, having a non‐empty proper subset (i.e. at least one but not all workers), will contribute an efficiency equal to the \(\gcd\) of its workers' efficiencies. The remaining workers will contribute an efficiency equal to the sum of their efficiencies. The total efficiency is the sum of these two contributions.

Your task is to determine the maximum total efficiency possible by optimally choosing the splitting of workers into these two groups.

Note: If there is only one worker, the answer is simply his/her efficiency.

The mathematical formulation for a split with group A and its complement B is:

\[ E = \gcd(\{a_i : i \in A\}) + \sum_{j \in B} a_j \]

Find the maximum E for each test case.

inputFormat

The input is read from stdin and has the following format:

T
N
a1 a2 ... aN
... (repeated for each test case)

Here, the first line is an integer T denoting the number of test cases. For each test case, the first line is an integer N (the number of workers), followed by a line with N integers representing the efficiencies.

outputFormat

For each test case, output a single line containing the maximum total efficiency, considering the optimal split of workers. The output should be printed to stdout.

## sample

2
4
12 15 18 24
3
3 6 9

69
18

</p>