Modular Circular Permutations

 You are given an array 

A=[A1,A2,…,AN]$A=[A_1,A_2,\dots ,A_N]$ containing distinct positive integers.

Let B$B$ be a permutation of A$A$. Define the value of B$B$ to be

∑i=1N(BimodBi+1)$$\sum _{i=1}^N(B_{i}mod{B}_{i+1})$$

where BN+1$B_{N+1}$ is treated to be B1$B_1$.

Find the maximum value across all permutations of A$A$.

Input Format

• The first line of input contains a single integer T$T$, denoting the number of test cases. The description of T$T$ test cases follows.
• Each test case consists of two lines of input.
• The first line of each test case contains an integer N$N$ — the size of A$A$.
• The second line of each test case contains N$N$ space-separated integers — the elements of A$A$.

Output Format

• For each test case, output a new line containing the answer — the maximum possible value across all permutations of A$A$.

Constraints

• 1≤T≤103$1\le T\le {10}^3$
• 2≤N≤2⋅103$2\le N\le 2\cdot {10}^3$
• 1≤Ai≤1015$1\le A_i\le {10}^{15}$
• Ai≠Aj$A_i\ne A_j$ for i≠j$i\ne j$
• The sum of N$N$ across all test cases won't exceed 2⋅103$2\cdot {10}^3$.

Sample Input 1 

2
2
5 13
4
11 5 14869010166 19007432007

Sample Output 1 

8
14869010184

Explanation

Test case 1$1$: The value of any permutation is (5mod13)+(13mod5)=5+3=8$(5mod13)+(13mod5)=5+3=8$.

Test case 2$2$: The 6$6$ cyclic permutations of the given array and their corresponding values are:

• [5,11,14869010166,19007432007]$[5,11,14869010166,19007432007]$ with value 14869010184$14869010184$
• [5,14869010166,11,19007432007]$[5,14869010166,11,19007432007]$ with value 28$28$
• [11,5,14869010166,19007432007]$[11,5,14869010166,19007432007]$ with value 14869010175$14869010175$
• [11,14869010166,5,19007432007]$[11,14869010166,5,19007432007]$ with value 20$20$
• [14869010166,5,11,19007432007]$[14869010166,5,11,19007432007]$ with value 4138421858$4138421858$
• [14869010166,11,5,19007432007]$[14869010166,11,5,19007432007]$ with value 4138421857$4138421857$

Among these, the highest value is 14869010184$14869010184$.