You are given an array $A$ of $N$ positive and pairwise distinct integers. 
You can permute the elements in any way you want. 
The cost of an ordering $(A_1, A_2, \ldots, A_N)$ is defined as $ (((A_1 \bmod A_2) \bmod A_3)......) \bmod A_N$ where $X \bmod Y$ means the remainder when $X$ is divided by $Y$. 
You need to find the maximum cost which can be attained through any possible ordering of the elements.

-----Input:-----
- The first line contains $T$ denoting the number of test cases.
- The first line of each testcase contains a single integer $N$. 
- The second line of each testcase contains $N$ space-separated integers, the elements of $A$. 

-----Output:-----
- For each testcase, output the maximum possible cost in a new line. 

-----Constraints-----
- $1 \leq T \leq 5*10^5$
- $2 \leq N \leq 5*10^5$
- $1 \leq A_i  \leq 10^9$
- Sum of $N$ over all testcases is less than or equal to $10^6$
- All elements in a single testcase are distinct.

-----Subtasks-----
- 100 points : Original constraints.

-----Sample Input:-----
1
2
7 12

-----Sample Output:-----
7

-----Explanation:-----
The two possible ways to order the elements are [7, 12] and [12, 7]. In the first case, the cost is $7 \bmod 12 = 7$ and in the second case the cost is $12 \bmod 7 = 5$. Clearly the answer is 7.

Difficulty: EASY

Starter code:

Solutions:
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(min(a))


for _ in range(int(input())):
	n = input()
	print(min([int(x) for x in input().split()]))


def weird(a):
	print(min(a))
for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split(' ')))
	weird(a)


for _ in range(int(input())):
	n = input()
	arr = list(map(int, input().split()))
	print(min(arr))


def weird_problem():
	return new[0]
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	new = sorted(a)
	print(weird_problem())


t = int(input())
for _ in range(t):
	n = int(input())
	array = list(map(int, input().split()))
	print(min(array))


t = int(input())
for it in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	x = a[0]
	for i in range(1, n):
		x = x % a[i]
	print(x)


T = int(input())
for _ in range(T):
	n = int(input())
	A = list(map(int, input().split()))
	A = sorted(A)
	print(A[0])


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = a[0] % a[1]
	for i in range(1, n):
		if d > a[i]:
			d = a[i] % d
		else:
			d = d % a[i]
	print(d)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = a[0] % a[1]
	for i in range(2, n):
		d = d % a[i]
	print(d)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if a.count(min(a)) > 1:
		print(max(a) % min(a))
	else:
		print(min(a))


t = int(input())
while t > 0:
	n = int(input())
	A = sorted(list(map(int, input().split())))
	print(A[0])
	t = t - 1


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	j = 1
	r = []
	b = a[0]
	while j < len(a):
		b = b % a[j]
		r.append(b)
		j += 1
	print(min(r))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = a[0] % a[1]
	m = a[1] % a[0]
	d = max(s, m)
	for i in range(2, n):
		if d > a[i]:
			d = a[i] % d
		else:
			d = d % a[i]
	print(d)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	print(l[0] % l[n - 1])


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l = sorted(l)
	print(l[0])


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = a[::-1]
	k = a[0]
	u = b[0]
	for i in range(1, n):
		k %= a[i]
	for j in range(1, n):
		u %= b[j]
	print(max(k, u))


t = int(input())
while t:
	n = int(input())
	a = list(map(int, input().split()))
	print(min(a))
	t -= 1


import os, sys, io, math
from re import *
from math import *
from array import *
from heapq import *
from bisect import *
from functools import *
from itertools import *
from statistics import *
from collections import *
I = lambda : [*map(int, sys.stdin.readline().split())]
IP = lambda : map(int, input().split())
IS = lambda : input()
IN = lambda : int(input())
IF = lambda : float(input())
for _ in range(IN()):
	(n, l) = (IN(), I())
	l.sort()
	r = l[0]
	for i in range(1, n):
		r %= l[i]
	print(r)


for i in range(int(input())):
	N = int(input())
	A = list(map(int, input().split(' ')))
	print(min(A))


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if 1 in a:
		print(1)
	elif sum(Counter(a).values()) == n:
		print(min(a))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = a[0]
	a.sort()
	for i in range(1, n):
		s = s % a[i]
	print(s)


for _ in range(int(input())):
	n = int(input())
	nums = [int(j) for j in input().split()]
	print(min(nums))


t = int(input())
for i in range(t):
	n = int(input())
	a = sorted(list(map(int, input().split())))
	b = a[0] % a[1]
	for n in a[2:]:
		b = b % n
	print(b)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	print(max(a[0] % a[n - 1], a[n - 1] % a[0]))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	print(l[0] % l[n - 1])


for _ in range(int(input())):
	b = int(input())
	a = list(map(int, input().split()))
	print(min(a))


n = int(input())
for i in range(n):
	n2 = int(input())
	l = list(map(int, input().split()))
	print(min(l))


t = int(input())
for r in range(t):
	n = int(input())
	s = input()
	a = list(map(int, s.split()))
	a.sort()
	p = a[0]
	for j in range(1, n):
		p = p % a[j]
	print(p)


s = int(input())
for i in range(s):
	a = int(input())
	n = list(map(int, input().split(' ')))
	n.sort()
	b = n[0]
	for j in range(a - 1):
		b = b % n[j + 1]
	print(b)


for i in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	a = sorted(a)
	x = min(a[0], a[1]) % max(a[0], a[1])
	for i in range(2, n):
		x = x % a[i]
	print(x)


for i in range(int(input())):
	a = int(input())
	li = list(map(int, input().split()))
	print(min(li))


for _ in range(int(input())):
	(N, A) = (int(input()), list(map(int, input().split())))
	a = A[0] % A[1]
	for i in range(2, N):
		a %= A[i]
	print(a)


a = int(input())
for i in range(a):
	b = int(input())
	list1 = list(map(int, input().split()))
	print(min(list1))


for i in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	print(min(x))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()[:n]))
	a.sort()
	x = a[0] % a[1]
	for i in range(2, n):
		k = x % a[i]
		x = k
	print(x)


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	A.sort()
	cost = A[0]
	for i in range(1, N):
		cost = cost % A[i]
	print(cost)


for _ in range(int(input())):
	N = int(input())
	L = sorted(map(int, input().split()))
	mod = L[0]
	for i in range(1, N):
		mod = mod % L[i]
	print(mod)


from itertools import permutations
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	print(min(arr))


t = int(input())
for j in range(t):
	n = int(input())
	s = list(map(int, input().split()))
	print(min(s))


x = int(input())
for i in range(0, x):
	s = int(input())
	u = list(map(int, input().split(' ')))
	print(min(u))


for _ in range(int(input())):
	arraylen = int(input())
	arraylist = list(map(int, input().split()))
	arraylist.sort()
	mod = arraylist[0]
	for i in range(1, arraylen):
		mod = mod % arraylist[i]
	print(mod)


for t in range(int(input())):
	N = int(input())
	a = list(map(int, input().split()))
	print(min(a))


from functools import reduce
for i in range(int(input())):
	num1 = int(input())
	list1 = list(map(int, input().split()))
	print(reduce(lambda a, b: a % b, list1))


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	d = 0
	m = l[0] % l[1]
	for i in range(2, n):
		d = m % l[i]
		m = d
	print(m)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	val = l[0] % l[1]
	for i in range(2, n):
		val = val % l[i]
	print(val)


T = int(input())
for T1 in range(T):
	n = int(input())
	a = []
	a = list(map(int, input().split()))
	print(min(a))


def sol():
	ans = 0
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	ans = max(a[0] % a[1], a[1] % a[0])
	return ans
for _ in range(int(input())):
	print(sol())


a = int(input())
for i in range(0, a):
	i = int(input())
	m = list(map(int, input().split()))
	o = min(m)
	print(o)


for _ in range(int(input())):
	N = int(input())
	l = list(map(int, input().split()))
	if l.count(min(l)) > 1:
		print(max(l) % min(l))
	else:
		print(min(l))


for i in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	print(min(arr))


for _ in range(int(input())):
	n = int(input())
	nums = sorted(list(map(int, input().split())))
	res = nums[0] % nums[1]
	for n in nums[2:]:
		res = res % n
	print(res)