题目内容

包装车间有长度为 $n$ 的正整数数组 $a$，第 $i$ 个工位当前的装箱规格为 $a_i$，总规格定义为所有元素之和。质检允许任意次调整：选出两个工位 $i$ 和 $j$，任选两个正整数 $x, y$ 满足 $\gcd(x, y) = \gcd(a_i, a_j)$，再令 $a_i \leftarrow x$、$a_j \leftarrow y$。车间希望在合法调整后让总规格尽可能小。

请计算经过任意次操作后，数组所有元素之和的最小值。

约束：测试组数 $T$ 满足 $1 \le T \le 10000$，$1 \le n \le 200000$，所有测试中 $n$ 的总和不超过 200000，$1 \le a_i \le 1000000000$。