Since Mansur is tired of making legends, there will be no legends for this task.

You are given an array of positive integer numbers $a_1, a_2, \ldots, a_n$. The elements of the array can be rearranged in any order. You need to find the smallest possible value of the expression $$\gcd(a_1) + \gcd(a_1, a_2) + \ldots + \gcd(a_1, a_2, \ldots, a_n),$$ where $\gcd(a_1, a_2, \ldots, a_n)$ denotes the greatest common divisor (GCD) of $a_1, a_2, \ldots, a_n$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single number $n$ ($1 \le n \le 10^5$) — the size of the array.

The second line of each test case contains $n$ numbers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^5$) — the initial array.

The sum of $n$ over all test cases does not exceed $10^5$.

The sum of $\max(a_1, a_2, \ldots, a_n)$ over all test cases does not exceed $10^5$.

Output

For each test case, output a single number on a separate line — the answer to the problem.

见题面 Input 部分

见题面 Output 部分

In the first test case, the elements can be rearranged as follows: $[2, 4, 2]$. Then the answer will be $\gcd(2) + \gcd(2, 4) + \gcd(2, 4, 2) = 2 + 2 + 2 = 6$.

In the third test case, the elements can be rearranged as follows: $[6, 10, 15]$. Then the answer will be $\gcd(6) + \gcd(6, 10) + \gcd(6, 10, 15) = 6 + 2 + 1 = 9$.