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: interview

Starter code:

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

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

# cook your dish here
for i in range(int(input())):
 n=int(input())
 x=list(map(int,input().split()))
 print(min(x))

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

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())
 nums = [int(j) for j in input().split()]
 print(min(nums))

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


# cook your dish here
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))



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

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


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

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 _ in range(int(input())):
 n=int(input())
 a=list(map(int,input().split()))
 d=a[0]%a[1]
 for i in range(2,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()))
 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)

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

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

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

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


# cook your dish here
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 _ 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)

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)

# cook your dish here
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)

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

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)