Prefix GCD

题目描述

给定一个正整数数组 $a_1, a_2, \ldots, a_n$。你可以任意重新排列数组中的元素。你需要找到如下表达式的最小可能值：

$$\gcd(a_1) + \gcd(a_1, a_2) + \ldots + \gcd(a_1, a_2, \ldots, a_n)$$

其中 $\gcd(a_1, a_2, \ldots, a_n)$ 表示 $a_1, a_2, \ldots, a_n$ 的最大公约数。

输入格式

每个测试点包含多组测试数据。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试数据组数。

每组测试数据的第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示数组的大小。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^5$），表示初始数组。

所有测试数据中 $n$ 的总和不超过 $10^5$。

所有测试数据中 $\max(a_1, a_2, \ldots, a_n)$ 的总和不超过 $10^5$。

输出格式

对于每组测试数据，输出一个整数，表示该组数据的答案。每个答案占一行。

输入输出样例 #1

输入 #1

5
3
4 2 2
2
6 3
3
10 15 6
5
6 42 12 52 20
4
42 154 231 66

输出 #1

6
6
9
14
51

说明/提示

在第一个测试用例中，元素可以重新排列为 $[2, 4, 2]$。此时答案为 $\gcd(2) + \gcd(2, 4) + \gcd(2, 4, 2) = 2 + 2 + 2 = 6$。

在第三个测试用例中，元素可以重新排列为 $[6, 10, 15]$。此时答案为 $\gcd(6) + \gcd(6, 10) + \gcd(6, 10, 15) = 6 + 2 + 1 = 9$。