给您一个包含 $$$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$$$。
输出
对于每个测试用例,输出一个整数——最小生成树的权重。
示例
输入复制
454 3 3 4 4102 10 3 2 9 9 4 6 4 61233 56 48 41 89 73 99 150 55 100 111 130711 45 14 19 19 8 10
输出复制
1 0 44 10
注意
在第一个测试用例中,连接边的一种可能方法是绘制边 $$$(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$$$。