CF2081D MST in Modulo Graph

You 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.

Each 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 $ .

For each test case, output a single integer — the weight of the minimum spanning tree.

In 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 $ .