Given an array A consisting of N non-negative integers. 

You need to perform the following operation (N - 1) times:
Sort the array A in ascending order.
Let M be the current size of the array A. Replace the array A by [(A_{2} - A_{1}), (A_{3} - A_{2}), \ldots ,(A_{M} - A_{M-1})]. Note that each time the operation is performed, the size of the array reduces by one.

Find the remaining element after (N-1) operations.

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

- The first line contains an integer T denoting number of test cases. The T test cases then follow.
- The first line of each test case contains an integer N - the size of the array.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \ldots, A_{N}.

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

For each test case, output single line: the remaining element after (N-1) operations.

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$0 ≤ A_{i} ≤ 10^{18}$
- Sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
2
4
29 19 0 3
1
777
----- Sample Output 1 ------ 
1
777
----- explanation 1 ------ 
- Test case 1: The operations look like:
- Operation $1$: Sort the array. Now, $A$ becomes $[0, 3, 19, 29]$. Replace the array. Thus, $A = [(3-0), (19-3), (29-19)] = [3, 16, 10]$.
- Operation $2$: Sort the array. Now, $A$ becomes $[3, 10, 16]$. Replace the array. Thus, $A = [(10-3), (16-10)] = [7, 6]$.
- Operation $3$: Sort the array. Now, $A$ becomes $[6, 7]$. Replace the array. Thus, $A = [(7-6)] = [1]$.

Thus, the remaining element after $3$ operations is $1$.

- Test case 2: Since $N = 1$, you don't need to perform any operation. The remaining element after $0$ operations is $777$.

Difficulty: VERY_HARD
Tags: Sorting
Skill types: Sorting

Starter code:

Solutions:
codechef = True
if codechef:
	import atexit, io, os, sys
	ss = io.BytesIO()
	_write = ss.write
	ss.write = lambda sett: _write(sett.encode())
	atexit.register(lambda : os.write(1, ss.getvalue()))
	y_in = open(0).read().split('\n')

	def y_inf():
		for y_id in range(len(y_in)):
			yield y_id
	y_ino = y_inf()
	input = lambda : y_in[next(y_ino)]
else:
	import sys
	input = sys.stdin.readline
import math, collections
inum = lambda : int(input())
imap = lambda : map(int, input().split())
itup = lambda : tuple(map(int, input().split()))
ilis = lambda : [int(zz) for zz in input().split()]
isor = lambda : sorted(map(int, input().split()))
idic = lambda : collections.defaultdict(lambda : 0)
tcs = 1 if not True else int(input())
for tc in range(1, tcs + 1):
	n = inum()
	arr = isor()
	zer = 0
	while len(arr) > 1:
		temp = []
		for i in range(len(arr) - 1):
			diff = arr[i + 1] - arr[i]
			if diff == 0:
				zer += 1
			else:
				temp.append(diff)
		if zer > 0:
			zer -= 1
			temp.append(0)
		arr = sorted(temp)
	print(arr[0] if arr else 0)


from math import inf
from collections import *
import math, os, sys, heapq, bisect, random, threading
from functools import lru_cache
from itertools import *

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def inpu():
	return int(inp())

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())
(M, M1) = (1000000007, 998244353)

def main():
	how_much_noob_I_am = 1
	how_much_noob_I_am = inpu()
	for _ in range(how_much_noob_I_am):
		n = inpu()
		arr = lis()
		extra = 0
		for i in range(n - 1):
			arr.sort(reverse=True)
			while arr and arr[-1] == 0:
				arr.pop()
				extra += 1
			for i in range(len(arr) - 1):
				arr[i] -= arr[i + 1]
			if extra:
				extra -= 1
			else:
				arr.pop()
		if extra:
			print(0)
		else:
			print(arr[0])
main()


p = int(input())
for i in range(p):
	x = int(input())
	y = [int(i) for i in input().split(' ')]
	s = 0
	for i in range(x - 1):
		y.sort(reverse=True)
		while y[-1] == 0:
			s += 1
			y.pop()
		for i in range(len(y) - 1):
			y[i] -= y[i + 1]
		if s:
			s -= 1
		else:
			y.pop()
	if s:
		print(0)
	else:
		print(y[0])


for _ in range(int(input())):
	n = int(input())
	a = [int(s) for s in input().split(' ')]
	zc = 0
	for i in range(n - 1):
		a.sort(reverse=True)
		while a[-1] == 0:
			zc += 1
			a.pop()
		for i in range(len(a) - 1):
			a[i] -= a[i + 1]
		if zc:
			zc -= 1
		else:
			a.pop()
	if zc:
		print(0)
	else:
		print(a[0])


import sys

def solve():
	(n,) = map(int, sys.stdin.readline().split())
	a = sorted(map(int, sys.stdin.readline().split()), reverse=True)
	assert n == len(a)
	for n in range(n - 1, 0, -1):
		for i in range(len(a) - 1):
			a[i] -= a[i + 1]
		if len(a) > n:
			a.pop()
		assert len(a) <= n
		a.sort(reverse=True)
		while len(a) > 1 and a[-1] == 0:
			a.pop()
	print(a[0])
(t,) = map(int, sys.stdin.readline().split())
for _ in range(t):
	solve()