You are given an array $A_{1}, A_{2}, \dots, A_{N}$ of length N. You can perform the following operation any number of times (possibly 0 times) :
Choose any two indices i and j and replace either A_{i} or A_{j} with $\gcd(A_{i},A_{j})$.

Find the minimum possible sum (ie. $A_{1} + A_{2} + \dots + A_{N})$ that you can achieve, and output that.

------ Input Format ------

• The first line of input will contain a single integer T, denoting the number of test cases.
• The first line of each test case contains an integer N - the length of the array A.
• The second line of each test case contains $N space-separated integers A_{1},A_{2},\ldots,A_{N}$.
  ​

------ Output Format ------

For each test case, output on a new line the minimum sum of the array that can be achieved.

------ Constraints ------

$1 ≤ T ≤ 100$
$2 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$
- The sum of $N$ over all test cases won't exceed $3 * 10^{5}$.

------ subtasks ------

Subtask 1 (10 points): $1 ≤ M ≤ 10$
Subtask 2 (20 points): The sum of $N$ across all test cases won't exceed $20$.
Subtask 3 (70 points): No further constraints.

----- Sample Input 1 ------
2
2
5 10
3
2 2 6

----- Sample Output 1 ------
10
6

----- explanation 1 ------
Test case $1$: Choose $i=1,j=2$ and replace $A_{2}$ with $\gcd(5,10)=5$.

Test case $2$: Choose $i=1,j=3$ and replace $A_{3}$ with $\gcd(2,6)=2$.

见题面

见题面