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.
Note
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$.
样例
5
3
4 2 2
2
6 3
3
10 15 6
5
6 42 12 52 20
4
42 154 231 66
6
6
9
14
51
题面与样例版权归 Codeforces 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。