Alice has an array A consisting of N distinct integers. Bob takes exactly N - 1 elements from this array and adds a positive integer X (i.e. X > 0) to each of these numbers and then shuffles them to form a new array B of length N - 1. 

You are given both arrays A and B. You have to identify the value of X chosen by Bob. If there are multiple possible values of X, print the smallest of them. It is guaranteed that for the given input, there exists at least one possible value of X.

Note: Since the input is large, prefer using fast input methods.

------ 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 contains 3 lines of input.
- The first line contains an integer N - the length of array A.
- The second line contains N space-separated integers A_{1}, A_{2}, \dots, A_{N}, denoting the array A.
- The third line contains N - 1 space-separated integers B_{1}, B_{2}, \dots, B_{N-1}, denoting the array B.

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

For each test case, output the value of X chosen by Bob. In case there are multiple possible values of X, print the smallest of them.

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

$1 ≤ T ≤ 7$
$2 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$
$1 ≤ B_{i} ≤ 2 \cdot 10^{9}$
$A_{1}, A_{2}, \dots, A_{N}$ are pairwise distinct.
$B_{1}, B_{2}, \dots, B_{N-1}$ are pairwise distinct.
- Sum of $N$ over all test cases does not exceed $5 \cdot 10^{5}$.

----- Sample Input 1 ------ 
3
4
1 4 3 8
15 8 11
2
4 8
10
2
2 4
3
----- Sample Output 1 ------ 
7
2
1
----- explanation 1 ------ 
Test case $1$: Bob takes the elements $\{1, 4, 8\}$ and adds $7$ to them to obtain a new sequence $\{8, 11, 15\}$. There is no other value of $X$ that can be added to the elements of $A$ to get $B$.

Test case $3$: There is only one option with Bob to consider, i.e. to take element $\{2\}$ and add $1$ to it to get array $B$. If he takes element $\{4\}$, he will have to add $-1$ which is not allowed.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Sorting

Mathematics


Solutions:
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort()
	b.sort()
	m = min(b) - min(a)
	M = max(b) - max(a)
	if M <= 0:
		print(m)
	elif n == 2:
		print(min(m, M))
	elif b[0] - a[1] == M:
		print(M)
	else:
		print(m)


for _ in range(int(input())):
	n = int(input())
	arr1 = list(map(int, input().split()))
	arr1.sort()
	arr2 = list(map(int, input().split()))
	arr2.sort()
	if n == 2:
		if arr2[0] > arr1[1]:
			print(arr2[0] - arr1[1])
		else:
			print(arr2[0] - arr1[0])
		continue
	arr3 = []
	arr4 = []
	for i in range(1, n - 1):
		arr3.append(arr1[i + 1] - arr1[i])
	for i in range(n - 2):
		arr4.append(arr2[i + 1] - arr2[i])
	if arr3 == arr4:
		if arr2[0] - arr1[1] > 0:
			print(arr2[0] - arr1[1])
		else:
			print(arr2[0] - arr1[0])
		continue
	else:
		print(arr2[0] - arr1[0])


from collections import *
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	x = float('inf')
	a.sort()
	b.sort()
	m = defaultdict(int)
	for i in range(n - 1):
		m1 = b[i] - a[i]
		m2 = b[i] - a[i + 1]
		if m1 != m2:
			if m1 > 0:
				m[m1] += 1
			if m2 > 0:
				m[m2] += 1
		elif m1 > 0:
			m[m1] += 1
	for i in m.keys():
		if m[i] == n - 1:
			x = min(x, i)
	print(x)


from collections import *
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort()
	b.sort()
	s = float('inf')
	d = defaultdict(int)
	for j in range(n - 1):
		m1 = b[j] - a[j]
		m2 = b[j] - a[j + 1]
		if m1 != m2:
			if m1 > 0:
				d[m1] += 1
			if m2 > 0:
				d[m2] += 1
		elif m1 > 0:
			d[m1] += 1
	for j in d.keys():
		if d[j] == n - 1:
			s = min(s, j)
	print(s)


import sys

def find_x(n, la, lb):
	la.sort()
	lb.sort()
	result = {}
	for i in range(n - 1):
		diff1 = lb[i] - la[i]
		diff2 = lb[i] - la[i + 1]
		if diff1 > 0:
			if diff1 in result:
				result[diff1] = result[diff1] + 1
			else:
				result[diff1] = 1
		if diff2 > 0:
			if diff2 in result:
				result[diff2] = result[diff2] + 1
			else:
				result[diff2] = 1
	for key in sorted(result.keys()):
		if result[key] == n - 1:
			return key
t = int(sys.stdin.readline().strip())
lines = sys.stdin.readlines()
for i in range(t):
	n = int(lines[i * 3])
	la = list((int(e) for e in lines[i * 3 + 1].split()))
	lb = list((int(e) for e in lines[i * 3 + 2].split()))
	result = find_x(n, la, lb)
	print(result)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort()
	b.sort()
	if n == 2:
		if b[0] > a[1]:
			print(b[0] - a[1])
		else:
			print(b[0] - a[0])
	else:
		s1 = b[0] - a[0]
		s2 = b[0] - a[1]
		if s1 > 0 and s2 > 0:
			cnt = 0
			i = 0
			j = 0
			while j < n and i < n - 1:
				if a[j] + s1 != b[i]:
					cnt += 1
					i -= 1
				if cnt >= 2:
					break
				i += 1
				j += 1
			cnt1 = 0
			i = 0
			j = 1
			while j < n and i < n - 1:
				if a[j] + s2 != b[i]:
					cnt1 += 1
					i -= 1
				if cnt1 >= 1:
					break
				i += 1
				j += 1
			if cnt1 == 0 and cnt == 1:
				print(min(s1, s2))
			elif cnt1 == 0:
				print(s2)
			else:
				print(s1)
		else:
			print(max(s1, s2))


def plag(a, b):
	c = max(b) - max(a)
	if c > 0:
		d = []
		for i in range(len(a)):
			d.append(a[i] + c)
		if sum(d) - sum(b) - c in a:
			return c
		else:
			a.remove(max(a))
			return max(b) - max(a)
	else:
		a.remove(max(a))
		return max(b) - max(a)
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	print(plag(a, b))


def alg(a, b):
	a = [int(i) for i in a]
	b = [int(i) for i in b]
	c = max(b) - max(a)
	if c > 0:
		d = [i + c for i in a]
		if sum(d) - sum(b) - c in a:
			return c
		else:
			a.remove(max(a))
			return max(b) - max(a)
	else:
		a.remove(max(a))
		return max(b) - max(a)
t = int(input())
a = []
b = []
for i in range(t):
	n = input()
	a.append(input().split())
	b.append(input().split())
for i in range(t):
	print(alg(a[i], b[i]))


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort()
	b.sort()
	if n == 2:
		print(b[0] - a[1] if b[0] - a[1] > 0 else b[0] - a[0])
	else:
		ans1 = 9999999999999
		ans2 = 9999999999999
		val1 = b[0] - a[0]
		val2 = b[-1] - a[-1]
		if val1 < 0:
			print(val2)
			continue
		if val2 < 0:
			print(val1)
			continue
		if val1 == val2:
			print(val1)
			continue
		myset = set(a)
		cnt1 = 0
		cnt2 = 0
		check1 = True
		check2 = True
		for val in b:
			if val - val1 not in myset:
				check1 = False
		for val in b:
			if val - val2 not in myset:
				check2 = False
		if check1 and val1 > 0:
			ans1 = val1
		if check2 and val2 > 0:
			ans2 = val2
		print(min(ans1, ans2))


def function():
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort()
	b.sort()
	if n == 2:
		print(b[0] - a[1]) if b[0] - a[1] > 0 else print(b[0] - a[0])
		return
	dif = []
	for i in range(3):
		for j in range(2):
			dif.append(b[j] - a[i])
	dif.sort()
	for i in range(5):
		if dif[i] == dif[i + 1] and dif[i] > 0:
			print(dif[i])
			return
t = int(input())
while t != 0:
	function()
	t -= 1


import math
import random
import statistics
import operator
import itertools
import sys
import copy
from collections import defaultdict, Counter, deque, OrderedDict
from heapq import heapify, heappush, heappop
from functools import lru_cache, reduce
from bisect import bisect_left, bisect_right
KPMOD1 = 1000000007
KPMOD2 = 998244353

def modinverse(a, mod):
	return binpow(a, mod - 2)

def mult(a, b):
	return a % KPMOD1 * (b % KPMOD1) % KPMOD1

def add(a, b):
	return (a % KPMOD1 + b % KPMOD1) % KPMOD1

def binpow(a, b):
	if b == 0:
		return 1
	res = binpow(a, b // 2) % KPMOD1
	if b % 2:
		return res * res * a % KPMOD1
	else:
		return res * res % KPMOD1

def fact(a):
	if a == 0 or a == 1:
		return 1
	return a * (fact(a) % KPMOD1) % KPMOD1

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def isPrime(n):
	if n == 1:
		return False
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True
MAX = 100
fact = [1] * MAX
invfact = [1] * MAX
for i in range(1, MAX):
	fact[i] = fact[i - 1] * i % KPMOD1
	invfact[i] = invfact[i - 1] * modinverse(i, KPMOD1) % KPMOD1

def factors(n):
	if n == 0:
		return set()
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))
for _ in range(int(input())):
	KPN = int(input())
	KPA = [int(x) for x in input().split()]
	KPB = [int(x) for x in input().split()]
	KPA.sort()
	KPB.sort()
	KPD = KPB[0] - KPA[1]
	KPF = 0
	for i in range(KPN - 1):
		if KPB[i] - KPA[i + 1] != KPD:
			KPF = 1
	if not KPF and KPD > 0:
		print(KPD)
	else:
		print(KPB[0] - KPA[0])


from collections import Counter
t = int(input())
for i in range(t):
	length = int(input())
	arr3 = []
	ans = float('inf')
	arr1 = list(map(int, input().split()))
	arr2 = list(map(int, input().split()))
	arr1.sort()
	arr2.sort()
	for i in range(length - 1):
		arr3.append(arr2[i] - arr1[i])
	for i in range(1, length):
		arr3.append(arr2[-i] - arr1[-i])
	arr4 = dict(Counter(arr3))
	for (k, v) in arr4.items():
		if v >= length - 1 and k > 0:
			ans = min(ans, k)
	print(ans)


import math
import bisect

class Fenwick_tree:

	def __init__(self, nums):
		self.N = len(nums)
		self.nums = nums
		self.fenwick = [0] * (self.N + 1)

	def inc(self, i, diff):
		i += 1
		while i <= self.N:
			self.fenwick[i] += diff
			i += i & -i

	def cumsum(self, i):
		res = 0
		while i > 0:
			res += self.fenwick[i]
			i -= i & -i
		return res

	def sumRange(self, low, hi):
		return self.cumsum(bisect.bisect_right(self.nums, hi)) - self.cumsum(bisect.bisect_left(self.nums, low))
t = int(input())
for i in range(t):
	n = int(input())
	arr1 = sorted([int(i) for i in input().split(' ')])
	sum1 = 0
	arr2 = sorted([int(i) for i in input().split(' ')])
	sum2 = 0
	ans = 0
	for i in range(n):
		sum1 += arr1[i]
	for i in range(n - 1):
		sum2 += arr2[i]
	for i in range(n):
		if sum2 - (sum1 - arr1[i]) <= 0:
			continue
		q = (sum2 - (sum1 - arr1[i])) % (n - 1)
		d = int((sum2 - (sum1 - arr1[i])) / (n - 1))
		if q == 0:
			k = 0
			invalid = False
			for j in range(n):
				if i == j:
					continue
				if arr2[k] - arr1[j] != d:
					invalid = True
				k += 1
			if invalid:
				continue
			ans = min(ans, d) if ans != 0 else d
	print(ans)


def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		arr1 = sorted([int(i) for i in input().split(' ')])
		sum1 = 0
		arr2 = sorted([int(i) for i in input().split(' ')])
		sum2 = 0
		ans = 0
		for i in range(n):
			sum1 += arr1[i]
		for i in range(n - 1):
			sum2 += arr2[i]
		for i in range(n):
			if sum2 - (sum1 - arr1[i]) <= 0:
				continue
			q = (sum2 - (sum1 - arr1[i])) % (n - 1)
			d = int((sum2 - (sum1 - arr1[i])) / (n - 1))
			if q == 0:
				k = 0
				invalid = False
				for j in range(n):
					if i == j:
						continue
					if arr2[k] - arr1[j] != d:
						invalid = True
					k += 1
				if invalid:
					continue
				ans = min(ans, d) if ans != 0 else d
		print(ans)
main()


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort()
	b.sort()
	c = []
	for i in range(len(b)):
		c.append([b[i] - a[i], b[i] - a[i + 1]])
	d = {}
	for i in c:
		for j in i:
			if j > 0:
				if j in d:
					d[j] += 1
				else:
					d[j] = 1
	m = 0
	ans = 0
	for i in d:
		if d[i] > m:
			m = d[i]
			ans = i
		if d[i] == m:
			ans = min(ans, i)
	print(ans)


from collections import *
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	b = [int(i) for i in input().split()]
	a.sort()
	b.sort()
	if n == 2:
		if b[0] > a[1]:
			print(b[0] - a[1])
		else:
			print(b[0] - a[0])
	else:
		(d1, d2, d3) = (defaultdict(int), defaultdict(int), defaultdict(int))
		d1[b[0] - a[0]] = 1
		f = 0
		for i in range(1, n - 1):
			if b[i] - a[i] not in d1:
				f = 1
			if f == 1:
				d1[b[i] - a[i + 1]] += 1
			else:
				d1[b[i] - a[i]] += 1
		for i in range(n - 1):
			d2[b[i] - a[i + 1]] += 1
		for i in range(n - 1):
			if i == 0:
				d3[b[i] - a[i]] += 1
			else:
				d3[b[i] - a[i + 1]] += 1
		ans = []
		for i in d1:
			if d1[i] >= n - 1:
				ans.append(i)
		for i in d2:
			if d2[i] >= n - 1:
				ans.append(i)
		for i in d3:
			if d3[i] >= n - 1:
				ans.append(i)
		ans.sort()
		if len(ans) >= 2:
			if ans[0] == 0:
				print(ans[1])
			else:
				print(ans[0])
		else:
			print(ans[0])


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort()
	b.sort()
	x = y = float('inf')
	if n == 2:
		x = b[0] - a[0] if b[0] - a[0] > 0 else float('inf')
		y = b[0] - a[1] if b[0] - a[1] > 0 else float('inf')
	else:
		if b[0] - a[0] > 0 and (b[0] - a[0] == b[1] - a[1] or b[0] - a[0] == b[1] - a[2]):
			x = b[0] - a[0]
		if b[0] - a[1] > 0 and b[0] - a[1] == b[1] - a[2]:
			y = b[1] - a[2]
	print(min(x, y))


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort()
	b.sort()
	l = []
	if n == 2:
		l.append(b[0] - a[0]) if b[0] - a[0] > 0 else None
		l.append(b[0] - a[1]) if b[0] - a[1] > 0 else None
	else:
		if b[0] - a[0] > 0 and (b[0] - a[0] == b[1] - a[1] or b[0] - a[0] == b[1] - a[2]):
			l.append(b[0] - a[0])
		if b[0] - a[1] > 0 and b[0] - a[1] == b[1] - a[2]:
			l.append(b[0] - a[1])
	print(min(l))


T = int(input())
for i in range(0, T):
	N = int(input())
	A = sorted([int(j) for j in input().split()])
	B = sorted([int(k) for k in input().split()])
	X = []
	if N == 2:
		if B[0] - A[0] > 0:
			X.append(B[0] - A[0])
		if B[0] - A[1] > 0:
			X.append(B[0] - A[1])
	else:
		if B[0] - A[0] > 0 and (B[0] - A[0] == B[1] - A[1] or B[0] - A[0] == B[1] - A[2]):
			X.append(B[0] - A[0])
		if B[0] - A[1] > 0 and B[0] - A[1] == B[1] - A[2]:
			X.append(B[0] - A[1])
	print(min(X))


for _ in range(int(input())):
	n = int(input())
	A = sorted(list(map(int, input().split())))
	B = sorted(list(map(int, input().split())))
	l = []
	if len(A) == 2:
		l.append(B[0] - A[0]) if B[0] - A[0] > 0 else None
		l.append(B[0] - A[1]) if B[0] - A[1] > 0 else None
	else:
		if B[0] - A[0] > 0 and (B[0] - A[0] == B[1] - A[1] or B[0] - A[0] == B[1] - A[2]):
			l.append(B[0] - A[0])
		if B[0] - A[1] > 0 and B[0] - A[1] == B[1] - A[2]:
			l.append(B[0] - A[1])
	print(min(l))


for _ in range(int(input())):
	n = int(input())
	d1 = map(int, input().split())
	d2 = map(int, input().split())
	ans = []
	if n == 2:
		(x, y) = d1
		a = list(d2)[0]
		if a > y:
			ans += [a - y]
		if a > x:
			ans += [a - x]
	else:
		(x, y, z, *trash) = sorted(d1)
		(a, b, *trash) = sorted(d2)
		if a - x > 0 and (a - x == b - y or a - x == b - z):
			ans += [a - x]
		if a - y > 0 and a - y == b - z:
			ans += [a - y]
	print(min(ans))


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort()
	b.sort()
	found1 = True
	poss1 = b[0] - a[0]
	used = False
	(i, j) = (0, 0)
	while i < n and j < n - 1:
		if b[j] - a[i] != poss1:
			if used:
				found1 = False
				break
			else:
				used = True
				i += 1
		else:
			i += 1
			j += 1
	if poss1 <= 0:
		found1 = False
	found2 = True
	poss2 = b[0] - a[1]
	used = False
	(i, j) = (0, 0)
	while i < n and j < n - 1:
		if b[j] - a[i] != poss2:
			if used:
				found2 = False
				break
			else:
				used = True
				i += 1
		else:
			i += 1
			j += 1
	if poss2 <= 0:
		found2 = False
	if found1 and found2:
		print(min(poss1, poss2))
	elif found1:
		print(poss1)
	else:
		print(poss2)


def solution(N, A, B):
	vote = {}
	for i in range(N // 2):
		diff_1 = B[i] - A[i]
		diff_2 = B[-(i + 1)] - A[-(i + 1)]
		if diff_1 > 0:
			if diff_1 not in vote:
				vote[diff_1] = 1
			else:
				vote[diff_1] += 1
		if diff_2 > 0:
			if diff_2 not in vote:
				vote[diff_2] = 1
			else:
				vote[diff_2] += 1
	max_votes = max(vote.values())
	print(min([k for (k, v) in vote.items() if v == max_votes]))
t = int(input())
for _ in range(t):
	N = int(input())
	A = sorted(list(map(int, input().split())))
	B = sorted(list(map(int, input().split())))
	solution(N, A, B)


t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	a = sorted([int(i.strip()) for i in input().split()])
	b = sorted([int(i.strip()) for i in input().split()])
	if n == 2:
		x = b[0] - a[0]
		d2 = b[0] - a[1]
		if d2 > 0 and d2 < x:
			x = d2
	else:
		d11 = b[0] - a[0]
		d22 = b[1] - a[1]
		d12 = b[0] - a[1]
		d23 = b[1] - a[2]
		if d11 == d22 or d11 == d23:
			x = d11
		if d12 == d23 and d12 > 0:
			x = d12
	print(x)


def mi():
	return map(int, input().split())

def li():
	return list(mi())

def si():
	return str(input())

def ni():
	return int(input())
from math import inf

def check(a, b, x):
	if x <= 0:
		return inf
	done = False
	for i in range(len(b)):
		if b[i] - a[i] != x:
			b.insert(i, a[i] + x)
			done = not done
			break
	flag = True
	if not done:
		b.append(a[-1] + x)
	for i in range(len(a)):
		if b[i] - a[i] != x:
			flag = False
	if flag:
		return x
	return inf
for t in range(int(input())):
	n = ni()
	a = li()
	b = li()
	a.sort()
	b.sort()
	(x, y) = (b[0] - a[0], b[0] - a[1])
	ansx = check(a.copy(), b.copy(), x)
	ansy = check(a, b, y)
	print(min(ansx, ansy))


t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(h) for h in input().split()]
	arr1 = [int(h) for h in input().split()]
	arr.sort()
	arr1.sort()
	u = arr[0] - arr1[0]
	v = arr[1] - arr1[0]
	u = -u
	v = -v
	u1 = [f + u for f in arr]
	v1 = [f + v for f in arr]
	u1 = sum(u1) - sum(arr1) - u
	v1 = sum(v1) - sum(arr1) - v
	flag1 = 0
	flag2 = 0
	if u1 in arr and u > 0:
		flag1 = 1
	if v1 in arr and v > 0:
		flag2 = 1
	if flag1 * flag2 == 1:
		print(min(u, v))
	elif flag1 == 1:
		print(u)
	else:
		print(v)


def decodeX(aliceArray, bobArray):
	if not isinstance(aliceArray, list) or not isinstance(bobArray, list):
		raise ValueError
	aliceArray.sort()
	bobArray.sort()
	deltaX1 = bobArray[0] - aliceArray[0]
	deltaX2 = bobArray[0] - aliceArray[1]
	if deltaX2 <= 0:
		return deltaX1
	for i in range(0, len(bobArray)):
		deltaX = bobArray[i] - aliceArray[i + 1]
		if deltaX != deltaX2:
			return deltaX1
	return deltaX2

def solve():
	input()
	aliceArray = list(map(int, input().split()))
	bobArray = list(map(int, input().split()))
	x = decodeX(aliceArray, bobArray)
	print(x)

def main():
	test_cases = int(input())
	for t in range(test_cases):
		solve()
main()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort()
	b.sort()
	if n == 2:
		if max(b) > max(a):
			print(max(b) - max(a))
		else:
			print(max(b) - min(a))
	else:
		x = max(a)
		y = max(b)
		d = y - x
		if d <= 0:
			print(y - a[len(a) - 2])
		elif d == b[len(b) - 2] - a[len(a) - 2] or d == b[len(b) - 2] - a[len(a) - 3]:
			print(d)
		else:
			print(y - a[len(a) - 2])


T = int(input())
for _ in range(T):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	a_min = min(a)
	a_max = max(a)
	b_min = min(b)
	b_max = max(b)
	min_diff = b_min - a_min
	max_diff = b_max - a_max
	result = None
	if min_diff == max_diff:
		result = min_diff
	else:
		a_sum = sum(a)
		b_sum = sum(b)
		n = len(b)
		result = min((x for (x, mx) in ((min_diff, a_max), (max_diff, a_min)) if x > 0 and b_sum - x * n == a_sum - mx))
	print(result)


T = int(input())
for _ in range(T):
	n = int(input())
	a_list = [int(x) for x in input().split()]
	b_list = [int(x) for x in input().split()]
	amin = min(a_list)
	amax = max(a_list)
	bmin = min(b_list)
	bmax = max(b_list)
	min_diff = bmin - amin
	max_diff = bmax - amax
	result = None
	if min_diff == max_diff:
		result = min_diff
	else:
		asum = sum(a_list)
		bsum = sum(b_list)
		n = len(b_list)
		result = min((x for (x, mx) in ((min_diff, amax), (max_diff, amin)) if x > 0 and bsum - x * n == asum - mx))
	print(result)


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort()
	b.sort()
	x1 = b[0] - a[0]
	x2 = b[0] - a[1]
	if x2 <= 0 or (n > 2 and b[1] - a[2] != x2):
		print(x1)
	else:
		print(x2)
	t -= 1


def result(A, B):
	dictionary = {}
	for i in range(len(A)):
		if str(A[i]) not in dictionary:
			dictionary[str(A[i])] = 1
		else:
			dictionary[str(A[i])] += 1
	maximum_A = max(A)
	maximum_B = max(B)
	possible_i_values = [maximum_B - maximum_A]
	A.remove(maximum_A)
	possible_i_values.append(maximum_B - max(A))
	possible_i_values = [x for x in possible_i_values if x > 0]
	final_vals = []
	for value in possible_i_values:
		dict2 = dictionary.copy()
		current_value = True
		for j in B:
			if str(j - value) in dict2:
				x = dict2[str(j - value)]
				if x == 0:
					current_value = False
					break
				dict2[str(j - value)] -= 1
			else:
				current_value = False
				break
		if current_value == True:
			final_vals.append(value)
	return min(final_vals)
for i in range(int(input())):
	ignore = input()
	A = [int(m) for m in input().split()]
	B = [int(m) for m in input().split()]
	result_ = result(A, B)
	print(str(result_))


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort()
	b.sort()
	x1 = b[0] - a[0]
	x2 = b[0] - a[1]
	if x2 <= 0 or (n > 2 and b[1] - a[2] != x2):
		print(x1)
	else:
		print(x2)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	lst = list(map(int, input().split()))
	l.sort()
	lst.sort()
	v1 = lst[0] - l[0]
	v2 = lst[0] - l[1]
	if v2 <= 0 or (n > 2 and lst[1] - l[2] != v2):
		print(v1)
	else:
		print(v2)


n = int(input())
for i in range(n):
	useless = int(input())
	n = list(map(int, input().split(' ')))
	j = list(map(int, input().split(' ')))
	n.sort()
	j.sort()
	jj = j[0] - n[0]
	nn = j[0] - n[1]
	if useless > 2 and j[1] - n[2] != nn or nn <= 0:
		print(jj)
	else:
		print(nn)


t = int(input())
for i in range(t):
	n = int(input())
	arr1 = list(map(int, input().split()))[:n]
	arr2 = list(map(int, input().split()))[:n - 1]
	arr1.sort()
	arr2.sort()
	ans1 = arr2[0] - arr1[0]
	ans2 = arr2[0] - arr1[1]
	if n > 2 and arr2[1] - arr1[2] != ans2 or ans2 <= 0:
		print(ans1)
	else:
		print(ans2)


for i in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	b = [int(i) for i in input().split()]
	a.sort()
	b.sort()
	temp = b[0] - a[1]
	flag = True
	for j in range(1, n - 1):
		if b[j] - a[j + 1] != temp:
			flag = False
	if temp <= 0 or flag == False:
		print(b[0] - a[0])
	else:
		print(b[0] - a[1])


t = int(input())
while t > 0:
	n = int(input())
	arr_original = list(map(int, input().split()))
	arr_result = list(map(int, input().split()))
	sum_original = sum(arr_original)
	sum_result = sum(arr_result)
	arr_original.sort()
	arr_result.sort()
	temp = {}
	for i in range(n):
		res = (sum_result - sum_original + arr_original[i]) // (n - 1)
		res_mod = (sum_result - sum_original + arr_original[i]) % (n - 1)
		if res_mod == 0 and res > 0:
			if res not in temp:
				temp[res] = [i]
			else:
				temp[res].append(i)
	var = []
	for i in temp:
		arr_dup = []
		for k in range(n):
			arr_dup.append(arr_original[k] + i)
		arr_dup_dup = arr_dup[:]
		for j in range(len(temp[i])):
			arr_dup.pop(temp[i][j])
			if arr_dup == arr_result:
				var.append(i)
			else:
				arr_dup = arr_dup_dup
	print(min(var))
	t -= 1


def get_dif(nums1, nums2):
	nums1.sort(reverse=True)
	nums2.sort(reverse=True)
	if len(nums1) == 2:
		if nums2[0] - nums1[0] > 0:
			return nums2[0] - nums1[0]
		else:
			return nums2[0] - nums1[1]
	if nums2[0] - nums1[0] == nums2[1] - nums1[1] and nums2[0] - nums1[0] > 0:
		return nums2[0] - nums1[0]
	if nums2[0] - nums1[0] == nums2[2] - nums1[1] and nums2[0] - nums1[0] > 0:
		return nums2[0] - nums1[0]
	return nums2[0] - nums1[1]
for _ in range(int(input())):
	input()
	nums1 = [int(x) for x in input().split()]
	nums2 = [int(x) for x in input().split()]
	d = get_dif(nums1, nums2)
	print(d)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort(reverse=True)
	b.sort(reverse=True)
	x = 0
	v1 = b[0] - a[0]
	v2 = b[0] - a[1]
	if v1 <= 0:
		x = v2
	elif v2 <= 0:
		x = v1
	else:
		sb = sum(b)
		sa = sum(a)
		if v1 * (n - 1) - (sb - sa) in a:
			x = v1
		else:
			x = v2
	print(x)


for z in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	a.sort()
	b.sort()
	m = 10 ** 9
	d = {}
	d[b[0] - a[0]] = 1
	p = b[n - 2] - a[n - 1]
	if p in d:
		d[p] += 1
	else:
		d[p] = 1
	for i in range(1, n - 1):
		p = b[i] - a[i]
		q = b[i] - a[i + 1]
		if p not in d:
			d[p] = 1
		else:
			d[p] += 1
		if q not in d:
			d[q] = 1
		else:
			d[q] += 1
	for x in d.keys():
		if x > 0 and d[x] >= n - 1:
			m = min(m, x)
	print(m)


import numpy
from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	a = sorted(list(map(int, input().split())))
	b = sorted(list(map(int, input().split())))
	if len(a) > 2:
		A = numpy.array(a[:-1] + a[1:])
		B = numpy.array(b + b)
		possible = [sol for (sol, cnt) in Counter(B - A).items() if cnt >= n - 1 and sol > 0]
		print(min(possible))
	else:
		x = b[0] - a[0]
		y = b[0] - a[1]
		if x > 0 and y > 0:
			print(min(x, y))
		elif x <= 0:
			print(y)
		else:
			print(x)


def identify_num(a, b, n):
	possible = []
	a_x = set(a)
	a_total = sum(a)
	b_total = sum(b)
	for val in a:
		if (b_total - (a_total - val)) % (n - 1) == 0 and (b_total - (a_total - val)) / (n - 1) > 0:
			x = int((b_total - (a_total - val)) / (n - 1))
			flag = True
			for itm in b:
				if itm - x not in a_x:
					flag = False
					break
			if flag:
				possible.append(x)
	return min(possible)
t = input()
for i in range(int(t)):
	n = int(input())
	a = input().split(' ')
	b = input().split(' ')
	a = list(map(lambda x: int(x), a))
	b = list(map(lambda x: int(x), b))
	print(identify_num(a, b, n))


import numpy
from collections import Counter

def readline():
	return list(map(int, input().split()))
for _ in range(int(input())):
	N = int(input())
	A = readline()
	B = readline()
	A.sort()
	B.sort()
	if N == 2:
		(x, y) = (B[0] - A[0], B[0] - A[1])
		if x >= 0 and y >= 0:
			print(min(x, y))
		elif x < 0:
			print(y)
		else:
			print(x)
	else:
		A = numpy.array(A[:-1] + A[1:])
		B = numpy.array(B + B)
		poss_sol = [sol for (sol, cnt) in Counter(B - A).items() if cnt >= N - 1 and sol > 0]
		print(min(poss_sol))


from collections import defaultdict
t = int(input())
while t:
	t -= 1
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort()
	b.sort()
	ans = 9999999999
	if n == 2:
		ans1 = b[0] - a[0]
		ans2 = b[0] - a[1]
		if ans1 > 0 and ans2 > 0:
			print(min(ans1, ans2))
		elif ans1 > 0:
			print(ans1)
		else:
			print(ans2)
	else:
		if b[0] > a[0] and b[0] - a[0] == b[1] - a[1]:
			ans = min(ans, b[0] - a[0])
		if b[0] > a[0] and b[0] - a[0] == b[1] - a[2]:
			ans = min(ans, b[0] - a[0])
		if b[0] > a[1] and b[0] - a[1] == b[1] - a[2]:
			ans = min(ans, b[0] - a[1])
		print(ans)


from collections import defaultdict
t = int(input())
for i in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	A.sort()
	B.sort()
	d = defaultdict(int)
	X = float('inf')
	for i in range(n - 1):
		x1 = B[i] - A[i]
		x2 = B[i] - A[i + 1]
		if x1 != x2:
			if x1 > 0:
				d[x1] += 1
			if x2 > 0:
				d[x2] += 1
		elif x1 > 0:
			d[x1] += 1
	for newX in d.keys():
		if d[newX] == n - 1:
			X = min(X, newX)
	print(X)


from sys import stdin, stdout
import sys

def fxn(n, arr1, arr2):
	arr1.sort()
	arr2.sort()
	for i in range(1, n + 1):
		x = arr2[-1] - arr1[-i]
		if n > 2:
			y = arr2[-2] - arr1[-(i + 1)]
		else:
			y = x
		if x > 0 and x == y:
			return x
		else:
			continue

def main():
	t = int(input())
	while t != 0:
		n = int(input())
		arr1 = [int(x) for x in input().split()]
		arr2 = [int(x) for x in input().split()]
		print(fxn(n, arr1, arr2))
		t -= 1
main()


for _ in range(int(input())):
	n = int(input())
	x = [int(i) for i in input().split()]
	y = [int(i) for i in input().split()]
	x.sort()
	y.sort()
	p = set(x)
	ans = y[0] - x[1]
	for i in y:
		if i - ans not in p:
			ans = y[0] - x[0]
			break
	if ans <= 0:
		ans = y[0] - x[0]
	print(ans)


import collections
import heapq
from pickle import FALSE
import sys
import math
import itertools
import bisect
from io import BytesIO, IOBase
import os

def values():
	return map(int, sys.stdin.readline().split())

def inlsts():
	return [int(i) for i in sys.stdin.readline().split()]

def inp():
	return int(sys.stdin.readline())

def instr():
	return sys.stdin.readline().strip()

def words():
	return [i for i in sys.stdin.readline().strip().split()]

def chars():
	return [i for i in sys.stdin.readline().strip()]

def solve():
	n = inp()
	l1 = sorted(values())
	l2 = sorted(values())
	x = l2[0] - l1[1]
	if x > 0:
		tmp = l2[0] - l1[1]
		for i in range(n - 1):
			if l2[i] - l1[i + 1] != tmp:
				print(l2[0] - l1[0])
				return
		print(x)
	else:
		print(l2[0] - l1[0])
for i in range(inp()):
	solve()


def solve():
	n = int(input())
	(a, b) = (list(map(int, input().split())), list(map(int, input().split())))
	a.sort()
	b.sort()
	if n == 2:
		ans1 = b[0] - a[-1]
		ans2 = b[0] - a[0]
		if ans1 > 0 and ans2 > 0:
			print(min(ans1, ans2))
		elif ans1 > 0:
			print(ans1)
		elif ans2 > 0:
			print(ans2)
	else:
		ans = 2 ** 63
		if b[0] > a[0] and b[0] - a[0] == b[1] - a[1]:
			ans = min(ans, b[0] - a[0])
		if b[0] > a[0] and b[0] - a[0] == b[1] - a[2]:
			ans = min(ans, b[1] - a[2])
		if b[0] > a[1] and b[0] - a[1] == b[1] - a[2]:
			ans = min(ans, b[0] - a[1])
		print(ans)
for _ in range(int(input())):
	solve()


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort()
	b.sort()
	ans = b[0] - a[1]
	d = defaultdict(lambda : 0)
	for i in a:
		d[i] += 1
	for i in b:
		if d[i - ans] == 0:
			ans = b[0] - a[0]
			break
	if ans <= 0:
		ans = b[0] - a[0]
	print(ans)


T = int(input())
for t in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	A.sort()
	B.sort()
	if N == 2:
		if A[0] < B[0] <= A[1]:
			print(B[0] - A[0])
		else:
			print(B[0] - A[1])
	else:
		anss = []
		cnds = []
		asum = sum(A)
		bsum = sum(B)
		for i in range(N):
			dif = (bsum - asum + A[i]) // (N - 1)
			mod = (bsum - asum + A[i]) % (N - 1)
			if dif > 0 and mod == 0:
				cnds.append((dif, i))
		for cn in cnds:
			f1 = True
			f2 = True
			for i in range(cn[1]):
				if B[i] - A[i] != cn[0]:
					f1 = False
					f2 = False
					break
			if f1:
				for i in range(cn[1] + 1, N):
					if B[i - 1] - A[i] != cn[0]:
						f2 = False
						break
			if f2:
				anss.append(cn[0])
		print(min(anss))


for _ in range(int(input())):
	n = int(input())
	a = sorted(map(int, input().split()))
	b = sorted(map(int, input().split()))
	if n == 2:
		if a[1] < b[0]:
			print(b[0] - a[1])
		else:
			print(b[0] - a[0])
	else:
		li = []
		if b[0] - a[0] > 0 and b[1] - a[1] > 0:
			if b[0] - a[0] == b[1] - a[1]:
				li.append(b[0] - a[0])
		if b[-1] - a[-1] > 0 and b[-2] - a[-2] > 0:
			if b[-2] - a[-2] == b[-1] - a[-1]:
				li.append(b[-1] - a[-1])
		print(min(li))


t = int(input())
for i in range(t):
	n = int(input())
	arr1 = list(map(int, input().split()[:n]))
	arr2 = list(map(int, input().split()[:n - 1]))
	arr1.sort()
	arr2.sort()
	s = set(arr1)
	ans = arr2[0] - arr1[1]
	for j in arr2:
		if j - ans not in s:
			ans = arr2[0] - arr1[0]
			break
	if ans <= 0:
		ans = arr2[0] - arr1[0]
	print(ans)