You are given an array A = [A_{1}, A_{2}, \ldots, A_{N}] containing distinct positive integers.

Let B be a [permutation] of A. Define the *value* of B to be
\sum_{i=1}^N (B_{i} \bmod{B_{i+1}})

where B_{N+1} is treated to be B_{1}.

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

------ Input Format ------ 

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

------ Output Format ------ 

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

------ Constraints ------ 

$1 ≤ T ≤ 10^{3}$
$2 ≤ N ≤ 2\cdot 10^{3}$
$1 ≤ A_{i} ≤ 10^{15}$
$A_{i} \neq A_{j}$ for $i \neq j$
- The sum of $N$ across all test cases won't exceed $2\cdot 10^{3}$.

----- Sample Input 1 ------ 
2
2
5 13
4
11 5 14869010166 19007432007

----- Sample Output 1 ------ 
8
14869010184

----- explanation 1 ------ 
Test case $1$: The value of any permutation is $(5 \bmod 13) + (13 \bmod 5) = 5 + 3 = 8$.

Test case $2$: The $6$ cyclic permutations of the given array and their corresponding values are:
- $[5, 11, 14869010166, 19007432007]$ with value $14869010184$
- $[5, 14869010166, 11, 19007432007]$ with value $28$
- $[11, 5, 14869010166, 19007432007]$ with value $14869010175$
- $[11, 14869010166, 5, 19007432007]$ with value $20$
- $[14869010166, 5, 11, 19007432007]$ with value $4138421858$
- $[14869010166, 11, 5, 19007432007]$ with value $4138421857$

Among these, the highest value is $14869010184$.

Source: codechef | Difficulty: VERY_HARD
Tags: Dynamic programming


Solutions:
import sys
import bisect
from bisect import bisect_left as lb
from bisect import bisect_right as rb
from queue import PriorityQueue
from queue import Queue
input_ = lambda : sys.stdin.readline().strip('\r\n')
from math import log
from math import gcd
from math import atan2, acos
from random import randint
import random
sa = lambda : input_()
sb = lambda : int(input_())
sc = lambda : input_().split()
sd = lambda : list(map(int, input_().split()))
sflo = lambda : list(map(float, input_().split()))
se = lambda : float(input_())
sf = lambda : list(input_())
flsh = lambda : sys.stdout.flush()
mod = 10 ** 9 + 7
mod1 = 998244353
gp = []
cost = []
dp = []
mx = []
ans1 = []
ans2 = []
special = []
specnode = []
a = 0
kthpar = []

def dfs2(root, par):
	if par != -1:
		dp[root] = dp[par] + 1
	for i in range(1, 20):
		if kthpar[root][i - 1] != -1:
			kthpar[root][i] = kthpar[kthpar[root][i - 1]][i - 1]
	for child in gp[root]:
		if child == par:
			continue
		kthpar[child][0] = root
		dfs(child, root)
ans = 0
a = []
(n, k) = (0, 0)
b = []
vis = []
tot = 0
time = []
time1 = []
adj = []
mx = -1
eps = 1e-07
gp = []
ans = []

def update_it(bit, i, val):
	n = len(bit)
	while i < n:
		bit[i] += val
		i += i & -i

def get_ans(bit, i):
	n = len(bit)
	tot = 0
	while i > 0:
		tot += bit[i]
		i -= i & -i
	return tot

def flip(a, l, r):
	for i in range(l, r):
		a[i] = '0' if a[i] == '1' else '1'
	return

def hnbhai(tc):
	n = sb()
	a = sd()
	a.sort()
	prefix = [0] * n
	for i in range(n):
		prefix[i] = a[i]
		if i > 0:
			prefix[i] += prefix[i - 1]
	dp = [-1] * n
	dp[n - 1] = 0
	for i in range(n - 2, -1, -1):
		for j in range(i + 1, n):
			dp[i] = max(dp[i], dp[j] + (prefix[j - 1] if j - 1 >= 0 else 0) - prefix[i] + a[j] % a[i])
	print(dp[0] + a[0])
	return
for _ in range(sb()):
	hnbhai(_ + 1)