CF2081D MST in Modulo Graph

给定一个包含 $n$ 个顶点的完全图，其中第 $i$ 个顶点的权值为 $p_i$。连接顶点 $x$ 和顶点 $y$ 的边的权重等于 $\operatorname{max}(p_x, p_y) \bmod \operatorname{min}(p_x, p_y)$。 请找出连接图中所有 $n$ 个顶点的 $n - 1$ 条边组成的集合的最小总权重。

每个测试包含多个测试用例。第一行输入测试用例数量 $t$（$1 \le t \le 10^4$）。接下来描述每个测试用例。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 5 \cdot 10^5$）。 每个测试用例的第二行包含 $n$ 个整数 $p_1, p_2, \ldots, p_n$（$1 \le p_i \le 5 \cdot 10^5$）。 保证所有测试用例的 $n$ 总和不超过 $5 \cdot 10^5$。 保证所有测试用例的 $\max(p_1,p_2,\ldots,p_n)$ 总和不超过 $5 \cdot 10^5$。

对于每个测试用例，输出一个整数表示最小生成树的总权重。

第一个测试用例中，一种可能的连接方式是选择边 $(1, 2)$、$(1, 4)$、$(1, 5)$、$(2, 3)$。第一条边的权重为 $\operatorname{max}(p_1, p_2) \bmod \operatorname{min}(p_1, p_2)=4 \bmod 3 = 1$，其他所有边的权重均为 $0$。 翻译由 DeepSeek R1 完成