题解

题面描述

给定一个长度为 $n$ 的数组 $\{a_1, a_2, \dots, a_n\}$，定义数组的权值为数组所有元素之和。你可以执行任意次以下操作，以使数组权值最小化：

• 选择两个索引 $i$ 和 $j$；
• 任意选取两个正整数 $x$ 和 $y$，但需满足$$\gcd(x, y) = \gcd(a_i, a_j);$$
• 将 $a_i \leftarrow x$，$a_j \leftarrow y$。

题目内容

给定一个长度为n的数组{$a_1, a_2, …, a_n$}，定义数组的权值为数组所有元素之和。你可以执行任意次以下操作，以使数组权值最小化：

• 选择两个索引 $i$ 和 $j$ ；
• 任意选取两个正整数 $x$ 和 $y$ ，但需满足 $gcd(x, y) = gcd(a_i, a_j)$；
• 将 $a_i ← x，a_i ← y$ 。

输入描述

每个测试文件均包含多组测试数据。 第一行输入一个整数 $T (1 ≤ T ≤ 10^4)$，表示测试组数；随后对于每组数据，依次输入： 第一行输入一个整数 $n (1 ≤ n ≤ 2×10^5)$ ，表示数组长度； 第二行输入 $n$ 个整数 $a_1, a_2, …, a_n (1 ≤ a_i ≤ 10^9)$ ，表示数组元素。此外，保证所有测试数据中 $∑n ≤ 2×10^5$ 。

输出描述

对于每个测试用例，在一行上输出一个整数，表示经过任意次操作后能够得到的最小数组权值。

样例1

输入

2
2
1 2
3
3 7 9

输出

2
3

说明

在第二个测试用例中，可以先选择 $(i, j) = (1, 2)$ ，$gcd(3, 7) = 1$ 。取 $x = y = 1$ 得到{$1, 1, 9$}； 再选择 $(i, j) = (2, 3)$ ，$gcd(1, 9) = 1$，取 $x = y = 1$ 得到{$1, 1, 1$}，权值为 $3$ 。