D. MST in Modulo Graphtime limit per test3 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputYou are given a complete graph with $$$n$$$ vertices, where the $$$i$$$-th vertex has a weight $$$p_i$$$. The weight of the edge connecting vertex $$$x$$$ and vertex $$$y$$$ is equal to $$$\operatorname{max}(p_x, p_y) \bmod \operatorname{min}(p_x, p_y)$$$.Find the smallest total weight of a set of $$$n - 1$$$ edges that connect all $$$n$$$ vertices in this graph.InputEach test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows. The first line of each test contains an integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$).The next line of each test contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le 5 \cdot 10^5$$$).The sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$.The sum of $$$\max(p_1,p_2,\ldots,p_n)$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$.OutputFor each test case, output a single integer — the weight of the minimum spanning tree.ExampleInput454 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 10Output1
0
44
10
NoteIn the first test case, one of the possible ways to connect the edges is to draw the edges $$$(1, 2)$$$, $$$(1, 4)$$$, $$$(1, 5)$$$, $$$(2, 3)$$$. The weight of the first edge is $$$\operatorname{max}(p_1, p_2) \bmod \operatorname{min}(p_1, p_2)=4 \bmod 3 = 1$$$, and the weights of all other edges are $$$0$$$.