For an upcoming programming contest, Roy is forming some teams from the students of his university. A team can have any number of contestants. 

Roy knows the skill level of each contestant. To make the teams work as a unit, he forms the teams based on some rules. Each of the team members must have a unique skill level for the team.  If a member's skill level is $x[i]$ where ${\mbox{0}}<i$, there exists another team member whose skill level is $x[i]-1$. Note that a contestant can write buggy code and thus can have a negative skill level.

The more contestants on the team, the more problems they can attempt at a time so Roy wants to form teams such that the smallest team is as large as possible.

For example, there are $n=7$ contestants with skill levels $skills=[-1,0,1,2,2,3]$.  There are many ways teams could be formed, e.g. [-1], [0],...,[3].  At the other end of the spectrum, we could form $team1=[-1,0,1,2,3]$ and $team2=[2]$.  We're looking for the largest smaller team size though.  Two sets that meet the criteria are $team1=[-1,0,1,2]$ and $team2=[2,3]$.  The largest smaller team size possible is $2$.

Note: There is an edge case where $\mbox{0}$ contestants have registered.  As no teams are to be created, the largest team created will have $\mbox{0}$ members.

Input Format

The first line contains an integer $\boldsymbol{\boldsymbol{t}}$, the number of test cases.

Each of the next $\boldsymbol{\boldsymbol{t}}$ lines contains a string of space-separated integers, $n$ followed by $n$ integers $x[i]$, a list of the contestants' skill levels.

Constraints

$1\leq t\leq100$ 

$0\leq n\leq10^{6}$ 

$-10^5\leq x[i]\leq10^5$ 

Output Format

For each test case, print the size of largest possible smallest team on a separate line.

Sample Input
4  
7 4 5 2 3 -4 -3 -5  
1 -4  
4 3 2 3 1  
7 1 -2 -3 -4 2 0 -1  

Sample Output
3
1
1
7

Explanation

For the first case, Roy can form two teams: one with contestants with skill levels {-4,-3,-5} and the other one with {4,5,2,3}. The first group containing 3 members is the smallest.  

In the second case, the only team is {-4}  

In the third case, the teams are {3} , {1,2,3}, the size of the smaller group being 1.

In the last case, you can build one group containing all of the contestants. The size of the group equals the total number of contestants.

Time limits  

Time limits for this challenge are given here

Note  

If n = 0, print 0.

Source: hackerrank | Difficulty: HARD
Tags: Greedy algorithms


Solutions:
import collections
import itertools

def answer(skills):
	if not skills:
		return 0
	finished_team_lengths = []
	current_team_starts = collections.deque()

	def go(s, c):
		while len(current_team_starts) < c:
			current_team_starts.append(s)
		while len(current_team_starts) > c:
			finished_team_lengths.append(s - current_team_starts.popleft())
	last_s = skills[0] - 1
	for (s, g) in itertools.groupby(skills):
		if s > last_s + 1:
			go(last_s + 1, 0)
		go(s, sum((1 for _ in g)))
		last_s = s
	go(last_s + 1, 0)
	return min(finished_team_lengths)
t = int(input())
for i in range(t):
	print(answer(sorted(map(int, input().split()[1:]))))


import sys
import heapq

class TeamSizeHeap(object):

	def __init__(self):
		self._data = []

	def push(self, team_size):
		heapq.heappush(self._data, team_size)

	def pop(self):
		return heapq.heappop(self._data)

	def top(self):
		return self._data[0]

	def empty(self):
		return len(self._data) == 0
T = int(sys.stdin.readline())
for _ in range(T):
	student_ranks = [int(x) for x in sys.stdin.readline().strip().split()][1:]
	student_ranks.sort()
	teams = {}
	for r in student_ranks:
		cands = teams.get(r - 1, None)
		if cands:
			smallest_team_size = cands.pop()
			if cands.empty():
				del teams[r - 1]
			if r in teams:
				teams[r].push(smallest_team_size + 1)
			else:
				h = TeamSizeHeap()
				h.push(smallest_team_size + 1)
				teams[r] = h
		elif r in teams:
			teams[r].push(1)
		else:
			h = TeamSizeHeap()
			h.push(1)
			teams[r] = h
	if not teams:
		print(0)
	else:
		min_size = min(teams.values(), key=lambda x: x.top()).top()
		print(min_size)


import sys
t = int(input())
for i in range(t):
	words = input().split()
	n = words[0]
	minTeamSize = 10000000000
	curTeams = []
	newCurTeams = []
	lastx = -10000000000
	members = [int(x) for x in words[1:]]
	members.sort()
	for x in members:
		if x > lastx:
			if x > lastx + 1:
				curTeams.extend(newCurTeams)
				newCurTeams = []
			for team in curTeams:
				if len(team) < minTeamSize:
					minTeamSize = len(team)
			curTeams = newCurTeams
			newCurTeams = []
			lastx = x
		minTeam = None
		minTeamLen = 10000000000
		for team in curTeams:
			if team[len(team) - 1] == x - 1:
				if len(team) < minTeamLen:
					minTeam = team
					minTeamLen = len(team)
		if minTeam != None:
			minTeam.append(x)
			curTeams.remove(minTeam)
			newCurTeams.append(minTeam)
		else:
			team = [x]
			newCurTeams.append(team)
	curTeams.extend(newCurTeams)
	for team in curTeams:
		if len(team) < minTeamSize:
			minTeamSize = len(team)
	print(minTeamSize if minTeamSize != 10000000000 else 0)


def partition(sorted_input):
	(partitions, current) = ([], [1])
	for (p, c) in zip(sorted_input, sorted_input[1:]):
		if c == p:
			current[-1] += 1
		elif c == p + 1:
			current.append(1)
		else:
			partitions.append(current)
			current = [1]
	partitions.append(current)
	return partitions

def smallest_size(counts):
	length = 0
	last_zero = 0
	for n in range(len(counts)):
		if counts[n] == 0:
			last_zero = n
			continue
		if n == len(counts) - 1 or counts[n] > counts[n + 1]:
			counts[n] -= 1
			length += 1
			break
		counts[n] -= 1
		length += 1
	return (length, counts[last_zero:])
for _ in range(int(input())):
	(_, *ns) = map(int, input().split())
	groups = partition(sorted(ns))
	best = len(ns)
	for group in groups:
		while True:
			(current, group) = smallest_size(group)
			if current == 0:
				break
			best = min(current, best)
	print(best)


from collections import Counter, deque

def main():
	(ncases,) = readints()
	for _ in range(ncases):
		contestants = readints()
		assert contestants[0] + 1 == len(contestants)
		print(0 if contestants[0] == 0 else min(teams(contestants[1:])))

def teams(contestants):
	ccount = Counter(contestants)
	s = sorted(ccount.keys())
	prev = s[0]
	prevcount = ccount[prev]
	deq = deque([prev] * prevcount)
	for level in s[1:]:
		levelcount = ccount[level]
		if prev + 1 == level:
			while prevcount < levelcount:
				deq.append(level)
				prevcount += 1
			while prevcount > levelcount:
				yield (level - deq.popleft())
				prevcount -= 1
		else:
			for _ in range(prevcount):
				yield (prev - deq.popleft() + 1)
			for _ in range(levelcount):
				deq.append(level)
		(prev, prevcount) = (level, levelcount)
	for _ in range(prevcount):
		yield (prev - deq.popleft() + 1)
	yield len(contestants)

def readints():
	return list(map(int, input().split()))
main()


numCases = int(input())

def contiguous(x, y):
	if x is None:
		return False
	return x + 1 == y

def update(freqCount, contiguous, minSoFar, tracked):
	if contiguous:
		if len(tracked) <= freqCount:
			newTracked = [0] * (freqCount - len(tracked)) + tracked
			tracked = [x + 1 for x in newTracked]
			return (tracked, minSoFar)
		else:
			tracked.sort()
			newTracked = tracked[:freqCount]
			removed = tracked[freqCount:]
			tracked = [x + 1 for x in newTracked]
			return (tracked, min(minSoFar, min(removed)))
	else:
		minSoFar = minSoFar if not tracked else min(minSoFar, min(tracked))
		tracked = [1] * freqCount
		return (tracked, minSoFar)
for _ in range(numCases):
	lst = [int(x) for x in input().split()[1:]]
	if len(lst) == 0:
		print(0)
	elif len(lst) == 1:
		print(1)
	else:
		lst.sort()
		prev = lst[0]
		freqCount = 1
		minSoFar = 99999999999999999
		tracked = []
		trackedHead = None
		for i in lst[1:]:
			if i == prev:
				freqCount += 1
			else:
				(tracked, minSoFar) = update(freqCount, contiguous(trackedHead, prev), minSoFar, tracked)
				trackedHead = prev
				prev = i
				freqCount = 1
		(tracked, minSoFar) = update(freqCount, contiguous(trackedHead, prev), minSoFar, tracked)
		minSoFar = minSoFar if not tracked else min(minSoFar, min(tracked))
		print(minSoFar)


import sys

def solve(A):
	if not A:
		return 0
	A.sort()
	print(A, file=sys.stderr)
	(prec, nbc, count) = (-10 ** 9 - 2, 0, [])
	i = 0
	while i < len(A):
		(j, a) = (1, A[i])
		while i + j < len(A) and A[i + j] == a:
			j += 1
		i += j
		if a != prec + 1:
			count.extend([1] * j)
		else:
			if j > nbc:
				count.extend([0] * (j - nbc))
			for k in range(j):
				count[-k - 1] += 1
		(nbc, prec) = (j, a)
	return min(count)
T = int(input())
for _ in range(T):
	print(solve([int(_) for _ in input().split()[1:]]))


def team_formation(my_list):
	my_list.sort()
	num_of_active_teams = 0
	smallest = len(my_list)
	team_sizes = []
	teams_needed = 0
	teams_active = 0
	last = my_list[0] - 2
	for m in my_list:
		if m == last:
			teams_needed += 1
		else:
			while teams_active > teams_needed:
				smallest = min(team_sizes[0], smallest)
				team_sizes = team_sizes[1:]
				teams_active -= 1
			if teams_active < teams_needed:
				team_sizes = team_sizes + [0] * (teams_needed - teams_active)
				teams_active = teams_needed
			team_sizes = [s + 1 for s in team_sizes]
			teams_needed = 1
			if m > last + 1:
				if len(team_sizes) > 0:
					smallest = min(smallest, team_sizes[-1])
				team_sizes = []
				teams_active = 0
			last = m
			if smallest == 1:
				return 1
	while teams_active > teams_needed:
		smallest = min(team_sizes[0], smallest)
		team_sizes = team_sizes[1:]
		teams_active -= 1
	team_sizes = [s + 1 for s in team_sizes]
	if teams_active < teams_needed:
		team_sizes = team_sizes + [1] * (teams_needed - teams_active)
		teams_active = teams_needed
	return min(team_sizes[-1], smallest)
t = int(input())
for i in range(t):
	w = list(map(int, input().split()))
	if w[0] == 0:
		print(0)
	else:
		l = w[1:]
		print(team_formation(l))


import sys
import operator
from collections import defaultdict

def main():
	sys.stdin.readline()
	for line in sys.stdin:
		skillCount = defaultdict(int)
		for skill in line.split()[1:]:
			skillCount[int(skill)] += 1
		print(findMin(sorted(skillCount), skillCount))

def findMin(keys, test):
	globalMin = float('inf')
	groups = []
	if len(keys) < 2:
		return len(keys)
	for i in range(len(keys) - 1):
		if keys[i] + 1 != keys[i + 1]:
			if len(groups) == 0:
				return 1
			globalMin = min(globalMin, groups[-1])
			groups = []
		else:
			if len(groups) == 0:
				groups = groups + [1] * test[keys[i]]
			if test[keys[i]] > test[keys[i + 1]]:
				for j in range(test[keys[i]] - test[keys[i + 1]]):
					globalMin = min(groups[0], globalMin)
					del groups[0]
				groups = list(map(lambda x: x + 1, groups))
			else:
				groups = list(map(lambda x: x + 1, groups))
				if test[keys[i]] < test[keys[i + 1]]:
					groups = groups + [1] * (test[keys[i + 1]] - test[keys[i]])
	if len(groups) != 0:
		return min(groups[-1], globalMin)
	return 1
main()


def counts(a):
	count = 0
	last = None
	for x in a:
		if last == None or last == x:
			count += 1
		elif last + 1 == x:
			yield (last, count)
			count = 1
		else:
			yield (last, count)
			yield (last + 1, 0)
			count = 1
		last = x
	if last is not None:
		yield (last, count)
		yield (last + 1, 0)
t = int(input())
for _ in range(t):
	a = sorted([int(x) for x in input().split()][1:])
	if len(a) == 0:
		print(0)
	else:
		fifo = []
		last = 0
		m = None
		for (x, n) in counts(a):
			if n > last:
				fifo += [x] * (n - last)
			elif n < last:
				delta = last - n
				dist = x - fifo[delta - 1]
				m = min(m, dist) if m is not None else dist
				fifo = fifo[delta:]
			last = n
		print(m)


import heapq

def team_formation(N, A):
	D = {}

	def insert(K, V):
		if K in D:
			D[K].append(V)
			heapq.heapify(D[K])
		else:
			D[K] = [V]
	for a in sorted(A):
		if a - 1 in D:
			W = heapq.heappop(D[a - 1])
			insert(a, W + 1)
			if not D[a - 1]:
				del D[a - 1]
		else:
			insert(a, 1)
	return min((heapq.heappop(D[d]) for d in D))

def main():
	T = int(input())
	for _ in range(T):
		I = [int(i) for i in input().split()]
		(N, A) = (I[0], I[1:])
		print(0 if N == 0 else team_formation(N, A))
main()


import collections

def debug(s):
	pass
for t in range(int(input())):
	people = list(map(int, input().split()))[1:]
	if len(people) == 0:
		print(0)
		continue
	people.sort()
	people.append('end')
	i = 0
	queue = collections.deque()
	smallest = 10 ** 6
	debug(people)
	last = people[i]
	while i < len(people) - 1:
		i2 = i + 1
		while people[i2] == people[i]:
			i2 += 1
		count = i2 - i
		debug('Adding {0} people to teams: {1}'.format(count, queue))
		while len(queue) > count:
			team = queue.popleft()
			debug('Closed team with {0} people'.format(team))
			if team < smallest:
				smallest = team
		if len(queue) < count:
			debug('Creating {0} new teams.'.format(count - len(queue)))
		while len(queue) < count:
			queue.append(0)
		debug('Giving each team a new member')
		queue = collections.deque(map(lambda x: x + 1, queue))
		if people[i2] != people[i] + 1:
			team = min(queue)
			debug('No person with skill {0}. Closing all teams. Minimum team size {1}.'.format(people[i] + 1, team))
			if team < smallest:
				smallest = team
			queue.clear()
		debug('Smallest team size {0}'.format(smallest))
		i = i2
	print(smallest)


from collections import Counter, deque

def pop(q, limit, pos):
	shortest = 10 ** 10
	while len(q) > limit:
		begin = q.popleft()
		shortest = min(shortest, pos - begin + 1)
	return shortest
T = int(input())
for _ in range(T):
	(n, *skill) = map(int, input().split())
	cnt = Counter(skill)
	q = deque()
	ans = 10 ** 10
	prev = None
	for (k, v) in sorted(cnt.items()):
		if prev is None:
			q.extend([k] * v)
		elif k != prev + 1:
			ans = min(ans, pop(q, 0, prev))
			q.extend([k] * v)
		elif v > len(q):
			q.extend([k] * (v - len(q)))
		else:
			ans = min(ans, pop(q, v, prev))
		prev = k
	ans = min(ans, pop(q, 0, prev))
	if ans == 10 ** 10:
		ans = 0
	print(ans)


n = int(input())
for _ in range(n):
	(k, *l) = map(int, input().split())
	if k == 0:
		print('0')
		continue
	ans = []
	li = sorted(l, reverse=True)
	ignore = 99999999999
	min = 9999999999
	lastRow = li[0]
	lastValue = li[0]
	for i in li:
		if i != lastValue:
			ignore = lastRow
		lastValue = i
		f = 0
		for k in ans:
			if k[0] > ignore:
				break
			if i >= k[0]:
				break
			if i == k[len(k) - 1] - 1:
				k.append(i)
				f = 1
				lastRow = k[0]
				break
			if i < k[len(k) - 1] - 1:
				if len(k) < min:
					min = len(k)
				ans.remove(k)
		if f == 0:
			ans.insert(0, [i])
	for k in ans:
		if len(k) < min:
			min = len(k)
	print(min)


def lineToArr(line):
	arr = [int(i) for i in line.split()]
	return arr

def toDict(arr):
	map = {}
	for x in arr:
		if not x in map:
			map[x] = 1
		else:
			map[x] += 1
	return map

def countHighestPlane(map):
	keys = sorted(map.keys())
	carryDict = {}
	for key in keys:
		if key not in carryDict:
			carryDict[key] = []
		if key - 1 not in carryDict:
			carryDict[key - 1] = []
		prev = carryDict[key - 1]
		for i in range(map[key]):
			if not len(prev):
				carryDict[key].insert(0, 1)
			else:
				m = prev.pop(0)
				carryDict[key].append(1 + m)
	res = min((min(x, default=1000000000) for x in carryDict.values()))
	return res
	elevation = map[keys[0]]
	lastKey = keys[0] - 1
	streak = 0
	lowestStreak = 10 ** 7
	for key in keys:
		if not lastKey + 1 == key:
			lowestStreak = min(streak, lowestStreak)
			streak = 0
		if elevation < map[key]:
			streak = 0
		streak += 1
		lastKey = key
		elevation = map[key]
	lowestStreak = min(streak, lowestStreak)
	return lowestStreak
lines = int(input())
for line in range(lines):
	line = input()
	arr = lineToArr(line)
	if arr[0] == 0:
		print(0)
		continue
	arr.pop(0)
	map = toDict(arr)
	result = countHighestPlane(map)
	print(result)


for t in range(int(input())):
	A = sorted(tuple(map(int, input().split()))[1:])
	teams = {}
	for n in A:
		if n - 1 in teams:
			new_size = teams[n - 1][-1] + 1
			teams[n - 1].pop()
			if not teams[n - 1]:
				del teams[n - 1]
			if n in teams:
				teams[n].append(new_size)
				teams[n].sort(reverse=True)
			else:
				teams[n] = [new_size]
		elif n in teams:
			teams[n].append(1)
		else:
			teams[n] = [1]
	minimum = len(A)
	for v in teams.values():
		minimum = min(minimum, *v)
	print(minimum)


def getMin(C):
	k = len(C)
	Inc = [(0, 1)]
	for i in range(1, k):
		if C[i] > C[i - 1]:
			Inc.append((i, C[i - 1] + 1))
	if len(Inc) == 1 and C[-1] == C[0]:
		return len(C)
	Dec = []
	for i in range(1, k):
		if C[i] < C[i - 1]:
			Dec.append(C[i - 1] - C[i])
		else:
			Dec.append(0)
	minCount = k
	for (i, d) in Inc:
		count = 1
		for dx in Dec[i:]:
			d -= dx
			if d <= 0:
				break
			count += 1
		if count < minCount:
			minCount = count
	return minCount
for _ in range(int(input())):
	A = [int(i) for i in input().strip().split()]
	if A[0] == 0:
		print('0')
		continue
	n = A.pop(0)
	A.sort()
	C = []
	smallest = n
	for i in range(n):
		if C:
			if A[i] == A[i - 1]:
				C[ind] += 1
			elif A[i] == A[i - 1] + 1:
				C.append(1)
				ind += 1
			else:
				val = getMin(C)
				if val < smallest:
					smallest = val
				C = [1]
				ind = 0
		else:
			C = [1]
			ind = 0
	if C:
		val = getMin(C)
		if val < smallest:
			smallest = val
	print(smallest)


from collections import Counter

def smallest_team(v):
	if v.pop(0) == 0:
		return 0
	c = Counter(v)
	smallest = len(v)
	starts = []
	last_level = min(v) - 1
	for i in sorted(c.keys()):
		if i > last_level + 1:
			smallest = min(smallest, last_level - starts[-1] + 1)
			starts = [i] * c[i]
		elif c[i] > len(starts):
			starts += [i] * (c[i] - len(starts))
		elif c[i] < len(starts):
			smallest = min(smallest, last_level - starts[len(starts) - c[i] - 1] + 1)
			starts = starts[len(starts) - c[i]:]
		last_level = i
	return min(smallest, last_level - starts[-1] + 1)
n = int(input())
for i in range(n):
	v = [int(x) for x in input().split()]
	print(smallest_team(v))


from collections import Counter

def ok(x):
	h = 0
	for i in range(1, L):
		if i - x >= 0 and ad[i - x] > 0:
			h -= ad[i - x]
		if ad[i] > 0:
			h += ad[i]
		if h > arr[i]:
			return False
	return True

def main():
	global arr, L, ad
	for _ in range(int(input())):
		a = list(map(int, input().split()))
		n = a[0]
		a = a[1:]
		a = list(Counter(a).items())
		a.sort()
		k = len(a)
		now = 0
		arr = [0]
		while now < k:
			arr.append(a[now][1])
			while now + 1 < k and a[now][0] + 1 == a[now + 1][0]:
				arr.append(a[now + 1][1])
				now += 1
			arr.append(0)
			now += 1
		ad = arr[:]
		L = len(arr)
		for i in range(1, L):
			ad[i] -= arr[i - 1]
		s = 1
		t = L - 1
		while s <= t:
			mid = s + t >> 1
			if ok(mid):
				s = mid + 1
			else:
				t = mid - 1
		print(t)
main()


T = int(input())
for T_i in range(T):
	l = [int(x) for x in input().split()]
	n = l[0]
	del l[0]
	l.sort()
	smallest = n
	if n == 0:
		print(0)
		continue
	counts = {}
	for i in l:
		if counts.__contains__(i):
			counts[i] += 1
		else:
			counts[i] = 1
	for i in l:
		if counts[i] > 0:
			am = counts[i]
			rise = am
			curr = 1
			counts[i] -= 1
			val = i + 1
			while counts.__contains__(val) and counts[val] >= rise:
				prevval = counts[val]
				counts[val] -= 1
				if prevval > rise:
					rise = prevval
				curr += 1
				val += 1
			if curr < smallest:
				smallest = curr
	print(smallest)


t = int(input())
for _ in range(t):
	students = [int(x) for x in input().split()][1:]
	if len(students) == 0:
		print(0)
		continue
	students.sort()
	smallest = len(students)
	i = 0
	prev = students.pop(i)
	size = 1
	multi = 1
	while students:
		if i < len(students) and prev + 1 == students[i]:
			if multi > 1:
				i += multi - 1
				if i < len(students) and prev + 1 == students[i]:
					prev = students.pop(i)
					size += 1
			else:
				prev = students.pop(i)
				size += 1
		elif i < len(students) and prev == students[i]:
			i += 1
			multi += 1
		else:
			smallest = min(smallest, size)
			i = 0
			prev = students.pop(i)
			size = 1
			multi = 1
			if smallest == 1:
				break
	print(min(smallest, size))


from itertools import islice

def frequencies(l):
	r = []
	for i in l:
		if r and i == r[-1][0]:
			r[-1][1] += 1
		else:
			r += ([i, 1],)
	return r

def group(l):
	r = []
	last = None
	for (n, f) in l:
		if last == n - 1:
			r[-1].append(f)
		else:
			r.append([f])
		last = n
	return r

def aux(inter):
	inter += (0, 0)
	inter = [inter[i] - inter[i - 1] for i in range(len(inter) - 1)]
	l = 0
	r = 1
	m = float('inf')
	while l < len(inter):
		if inter[l] == 0:
			l += 1
		else:
			while inter[r] >= 0:
				r += 1
			m = min(m, r - l)
			inter[r] += 1
			inter[l] -= 1
	return m

def main(l):
	l.sort()
	return min((aux(inter) for inter in group(frequencies(l))), default=0)
for i in range(int(input())):
	print(main(list(map(int, islice(input().split(), 1, None)))))


t = int(input())
for test in range(t):
	(n, *a) = map(int, input().split())
	a = sorted(a)
	if n == 0:
		print(0)
		continue
	result = n
	gindex = 0
	teams = []
	prev_value = -1
	while gindex < len(a):
		i = gindex
		while i < len(a) - 1 and a[i] == a[i + 1]:
			i += 1
		counter = i + 1 - gindex
		value = a[gindex]
		if gindex == 0:
			teams.append([1, counter])
		elif value == prev_value + 1:
			index = len(teams) - 1
			while index >= 0:
				if counter > teams[index][1]:
					teams[index][0] += 1
					counter -= teams[index][1]
				elif counter == teams[index][1]:
					if index > 0:
						result = min(result, teams[index - 1][0])
					teams[index][0] += 1
					teams = teams[index:]
					break
				elif counter < teams[index][1]:
					result = min(result, teams[index][0])
					teams[index][0] += 1
					teams[index][1] = counter
					teams = teams[index:]
					break
				index -= 1
			else:
				teams.append([1, counter])
		else:
			result = min(result, teams[-1][0])
			teams = [[1, counter]]
		prev_value = value
		gindex = i + 1
	result = min(result, teams[-1][0])
	print(result)


t = int(input().strip())
for i_t in range(t):
	nums = [int(i) for i in input().strip().split(' ')]
	n = nums[0]
	if n == 0:
		print(0)
		continue
	leveldict = {}
	levels = nums[1:]
	for i in levels:
		if i in leveldict:
			leveldict[i] += 1
		else:
			leveldict[i] = 1
	minlength = 10 ** 9
	candidates = []
	keys = sorted(list(leveldict.keys()))
	prev_level = -2000000000
	for level in keys:
		levelsize = leveldict[level]
		if prev_level != level - 1:
			prev_level = level
			if len(candidates) > 0:
				minlength = min(minlength, min(candidates))
			candidates = [1] * levelsize
			continue
		prev_level = level
		if len(candidates) <= levelsize:
			candidates = [1] * (levelsize - len(candidates)) + [i + 1 for i in candidates]
		elif len(candidates) > levelsize:
			minlength = min(minlength, min(candidates[levelsize:]))
			candidates = [i + 1 for i in candidates[0:levelsize]]
	if len(candidates) > 0:
		minlength = min(minlength, min(candidates))
	print(minlength)


t = int(input())

def insert(data_, si, i):
	if si not in data_:
		data_[si] = [i]
	else:
		data_[si].append(i)
while t:
	t -= 1
	numbers = [int(x) for x in input().split()]
	if numbers[0] == 0:
		print(0)
		continue
	s = numbers[1:]
	s.sort()
	data = {}
	for i in range(numbers[0]):
		prev_number = s[i] - 1
		if prev_number not in data:
			if s[i] not in data:
				data[s[i]] = [1]
			else:
				data[s[i]].append(1)
		elif len(data[prev_number]) == 1:
			insert(data, s[i], data[prev_number][0] + 1)
			del data[prev_number]
		else:
			data[prev_number].sort()
			insert(data, s[i], data[prev_number][0] + 1)
			del data[prev_number][0]
	result = min([min(x) for x in data.values()])
	print(result)


import sys
t = int(input())

def d(*args):
	pass

class solver(object):

	def __init__(self, num):
		self.startingpoints = []
		self.nextclose = 0
		self.last = None
		self.lastnum = 0
		self.shortest = num

	def apply(self, value, count):
		d('Applying', count, 'counts of', value)
		if value - 1 != self.last:
			self.stop(self.lastnum, self.last)
			self.lastnum = 0
		if count == self.lastnum:
			d("Same size, don't need to alter the set of teams")
			self.last = value
			return
		elif curnum < self.lastnum:
			self.stop(self.lastnum - count, self.last)
		else:
			self.start(count - self.lastnum, value)
		self.last = value
		self.lastnum = count

	def stop(self, amount, value):
		d('Finishing', amount, 'old teams')
		for k in range(amount):
			d('Closing team from', self.startingpoints[self.nextclose], 'to', value)
			if value - self.startingpoints[self.nextclose] + 1 < self.shortest:
				self.shortest = value - self.startingpoints[self.nextclose] + 1
				d('New smallest team size is', self.shortest)
			self.nextclose += 1

	def start(self, amount, value):
		d('Starting', amount, 'new teams')
		for k in range(amount):
			self.startingpoints.append(value)

	def finish(self):
		self.stop(self.lastnum, self.last)
for i in range(t):
	(n, *entrants) = map(int, input().split())
	if not n:
		print(0)
		continue
	entrants.sort()
	d('Finding smallest team amidst', n, 'contestants:', entrants)
	nextclose = 0
	lastnum = 0
	last = None
	curnum = 0
	s = solver(n)
	for j in entrants:
		if j == last:
			curnum += 1
		else:
			if last is not None:
				s.apply(last, curnum)
			last = j
			curnum = 1
	s.apply(last, curnum)
	s.finish()
	d('Smallest team size is', s.shortest)
	d('')
	print(s.shortest)


import sys
from collections import OrderedDict
__author__ = 'alessandro'

def get_smallest_team_size(n, students_):
	if n == 0:
		return 0
	students = OrderedDict()
	for s in sorted(students_):
		if s in students:
			students[s] += 1
		else:
			students[s] = 1
	previous_student = None
	buffers = []
	min_size = sys.maxsize
	for (s, count) in students.items():
		num_buffers = len(buffers)
		if previous_student is not None and s == previous_student + 1:
			if count == num_buffers:
				for buffer in buffers:
					buffer.append(s)
			elif count < num_buffers:
				min_size = min(min_size, min([len(x) for x in buffers[:num_buffers - count]]))
				buffers = buffers[num_buffers - count:]
				for buffer in buffers:
					buffer.append(s)
			else:
				for buffer in buffers:
					buffer.append(s)
				for _ in range(count - num_buffers):
					buffers.append([s])
		else:
			if num_buffers > 0:
				min_size = min(min_size, min([len(x) for x in buffers]))
			buffers = [[s] for _ in range(count)]
		previous_student = s
	return min(min_size, min([len(x) for x in buffers]))

def main(_):
	num_tests = int(input().strip())
	for _ in range(num_tests):
		entries = [int(x) for x in input().strip().split()]
		print(get_smallest_team_size(entries[0], entries[1:]))
main(sys.argv)


import heapq

def pop_from(dict, key):
	val = heapq.heappop(dict[key])
	if len(dict[key]) == 0:
		del dict[key]
	return val

def push_into(dict, key, value):
	if key not in dict:
		dict[key] = []
		heapq.heapify(dict[key])
	heapq.heappush(dict[key], value)
t = int(input())
for _ in range(t):
	A = list(map(int, input().split()))
	n = A[0]
	if n == 0:
		print(0)
	else:
		A = sorted(A[1:])
		teams = {}
		for i in range(n):
			if A[i] - 1 in teams:
				size = pop_from(teams, A[i] - 1)
				push_into(teams, A[i], size + 1)
			else:
				push_into(teams, A[i], 1)
		min_size = 999999
		for each in teams.values():
			min_pot = min(each)
			if min_pot < min_size:
				min_size = min_pot
		if min_size != 999999:
			print(min_size)


def count(c):
	res = len(c)
	for i in range(len(c) - 1, 0, -1):
		while c[i] > c[i - 1]:
			l = 0
			while i + l < len(c) and c[i + l] > 0:
				c[i + l] -= 1
				l += 1
			res = min(res, l)
	return res
for _ in range(int(input())):
	m = map(int, input().split())
	n = next(m)
	if n == 0:
		print(0)
		continue
	l = sorted(m)
	ans = n
	c = [0, 1]
	for i in range(1, n):
		if l[i] == l[i - 1]:
			c[-1] += 1
		elif l[i] == l[i - 1] + 1:
			c.append(1)
		else:
			ans = min(ans, count(c))
			c = [0, 1]
	ans = min(ans, count(c))
	print(ans)


n = int(input().strip())
if n == 0:
	print('0')
	sys.exit(0)
for student_group in range(0, n):
	line = [int(x) for x in input().strip().split(' ')]
	m = line[0]
	s = line[1:]
	ss = list()
	d0 = dict()
	for skill in s:
		try:
			d0[skill] += 1
		except KeyError:
			d0[skill] = 1
			ss.append(skill)
	ss = sorted(ss)
	groups = list()
	prev_skill = None
	l = 0
	i = 0
	while len(ss):
		if i >= len(ss):
			groups.append(l)
			if l == 1:
				break
			i = 0
			l = 0
			prev_skill = None
		if i > 0:
			if prev_skill and ss[i] != prev_skill + 1:
				groups.append(l)
				if l == 1:
					break
				i = 0
				l = 0
				prev_skill = None
			elif d0[ss[i]] > d0[ss[i - 1]]:
				l += 1
				prev_skill = ss[i]
				d0[ss[i]] -= 1
				if d0[ss[i]] == 0:
					ss.pop(i)
				else:
					i += 1
			else:
				groups.append(l)
				if l == 1:
					break
				i = 0
				l = 0
				prev_skill = None
		elif i == 0:
			if prev_skill and ss[i] != prev_skill + 1:
				groups.append(l)
				if l == 1:
					break
				i = 0
				l = 0
			l += 1
			prev_skill = ss[i]
			d0[ss[i]] -= 1
			if d0[ss[i]] == 0:
				ss.pop(i)
			else:
				i += 1
	groups.append(l)
	print(min(groups))


n_cases = int(input())
for case in range(n_cases):
	vals = list(map(int, input().split()))
	if vals[0] == 0:
		print(0)
		continue
	vals = vals[1:]
	vals.sort()
	teams_dict = {vals[0]: [1]}
	for val in vals[1:]:
		if val - 1 not in teams_dict:
			if val not in teams_dict:
				teams_dict[val] = [1]
			else:
				teams_dict[val].append(1)
				teams_dict[val].sort()
		else:
			new_count = teams_dict[val - 1][0] + 1
			teams_dict[val - 1] = teams_dict[val - 1][1:]
			if not teams_dict[val - 1]:
				del teams_dict[val - 1]
			else:
				teams_dict[val - 1].sort()
			if val not in teams_dict:
				teams_dict[val] = [new_count]
			else:
				teams_dict[val].append(new_count)
				teams_dict[val].sort()
	min_group_size = float('Inf')
	for key in teams_dict:
		for group_size in teams_dict[key]:
			if group_size < min_group_size:
				min_group_size = group_size
	print(min_group_size)


for _ in range(int(input())):
	minLen = -1
	data = list(map(int, input().split()))
	if len(data) == 1:
		print('0')
		continue
	data = sorted(data[1:])
	cList = []
	pList = []
	prev = None
	for v in data:
		if prev == None:
			cList.append(1)
		elif v == prev:
			if len(pList) > 0:
				minV = min(pList)
				pList.remove(minV)
				cList.append(minV + 1)
			else:
				cList.append(1)
		elif abs(v - prev) > 1:
			if len(pList) > 0:
				if minLen == -1:
					minLen = min(pList)
				else:
					minLen = min(min(pList), minLen)
			if len(cList) > 0:
				if minLen == -1:
					minLen = min(cList)
				else:
					minLen = min(min(cList), minLen)
			pList = []
			cList = [1]
		else:
			if len(pList) > 0:
				if minLen == -1:
					minLen = min(pList)
				else:
					minLen = min(minLen, min(pList))
			pList = cList
			minV = min(pList)
			pList.remove(minV)
			cList = [minV + 1]
		prev = v
	if len(pList) > 0:
		if minLen == -1:
			minLen = min(pList)
		else:
			minLen = min(min(pList), minLen)
	if len(cList) > 0:
		if minLen == -1:
			minLen = min(cList)
		else:
			minLen = min(min(cList), minLen)
	print(minLen)


from collections import Counter

def solve(N, A):
	if N == 0:
		return 0
	counts = Counter(A)
	levels = sorted(counts)
	changes = []
	old_level = levels[0] - 1
	old_count = 0
	for level in levels:
		count = counts[level]
		if level - old_level > 1:
			changes.append((old_level + 1, -old_count))
			changes.append((level, count))
		elif count != old_count:
			changes.append((level, count - old_count))
		old_level = level
		old_count = count
	changes.append((level + 1, -count))

	def ups():
		for (level, change) in changes:
			if change > 0:
				for _ in range(change):
					yield level

	def downs():
		for (level, change) in changes:
			if change < 0:
				for _ in range(-change):
					yield level
	shortest = levels[-1] + 1 - levels[0]
	for (u, d) in zip(ups(), downs()):
		shortest = min(shortest, d - u)
	return shortest
t = int(input())
for _ in range(t):
	R = [int(x) for x in input().split()]
	(N, A) = (R[0], R[1:])
	print(solve(N, A))


import sys
import heapq

def min_team_num(arr):
	arr = sorted(arr)
	n = len(arr)
	min_size = 100000
	heap = [(arr[0], 1)]
	for i in range(1, n):
		t = arr[i]
		min_group = heapq.heappop(heap)
		while heap and min_group[0] < t - 1:
			if min_group[1] < min_size:
				min_size = min_group[1]
			min_group = heapq.heappop(heap)
		if t == min_group[0] + 1:
			new_group = (t, min_group[1] + 1)
			heapq.heappush(heap, new_group)
		elif t == min_group[0]:
			new_group = (t, 1)
			heapq.heappush(heap, min_group)
			heapq.heappush(heap, new_group)
		else:
			if min_group[1] < min_size:
				min_size = min_group[1]
			new_group = (t, 1)
			heapq.heappush(heap, new_group)
	while heap:
		min_group = heapq.heappop(heap)
		if min_group[1] < min_size:
			min_size = min_group[1]
	print(min_size)
	return
t = int(input().strip())
for i in range(t):
	arr = [int(at) for at in input().strip().split(' ')]
	if arr[0] == 0:
		print(0)
	elif arr[0] == 1:
		print(1)
	else:
		min_team_num(arr[1:])


import collections
t = int(input())
for case in range(t):
	skill = [int(x) for x in input().split()]
	n = skill[0]
	del skill[0]
	skill.sort()
	i = 0
	prev = 0
	active = collections.deque()
	min_team = n
	while i < n:
		x = skill[i]
		j = i + 1
		while j < n and skill[j] == x:
			j += 1
		num = j - i
		i = j
		while prev < num:
			active.append(x)
			prev += 1
		while prev > num:
			team = x - active.popleft()
			if team < min_team:
				min_team = team
			prev -= 1
		if i == n or skill[i] > x + 1:
			while num > 0:
				team = x - active.popleft() + 1
				if team < min_team:
					min_team = team
				num -= 1
		prev = num
	print(min_team)


import heapq

def team(iq):
	teamD = {}

	def insert(key, value):
		if key in teamD:
			teamD[key].append(value)
			heapq.heapify(teamD[key])
		else:
			teamD[key] = [value]
	for i in sorted(iq):
		if i - 1 in teamD:
			temp = heapq.heappop(teamD[i - 1])
			insert(i, temp + 1)
			if not teamD[i - 1]:
				del teamD[i - 1]
		else:
			insert(i, 1)
	return min((heapq.heappop(teamD[j]) for j in teamD))

def main():
	T = int(input())
	for _ in range(T):
		L = [int(x) for x in input().split()]
		N = L[0]
		A = L[1:]
		if N == 0:
			print(0)
		else:
			print(team(A))
main()


def is_sorted(t1, t2):
	if t1[1] > t2[1]:
		return True
	return t1[1] == t2[1] and t1[0] >= t2[0]

def sorting(temporal):
	actual = len(temporal) - 1
	while actual > 0 and (not is_sorted(temporal[actual], temporal[actual - 1])):
		(temporal[actual], temporal[actual - 1]) = (temporal[actual - 1], temporal[actual])
		actual -= 1

def formGroups(contestans):
	if len(contestans) == 0:
		print(0)
		return
	contestans.sort()
	results = []
	temporal = []
	for cont in contestans:
		added = False
		for t in temporal[:]:
			(size, high) = t
			if high < cont - 1:
				temporal.remove(t)
				results.append(t)
			elif high == cont - 1:
				temporal.remove(t)
				temporal.append((t[0] + 1, cont))
				added = True
				break
			else:
				break
		if not added:
			temporal.append((1, cont))
		sorting(temporal)
	results += temporal
	min = results[0][0]
	for x in range(1, len(results)):
		if results[x][0] < min:
			min = results[x][0]
	print(min)
test_cases = int(input())
for i in range(test_cases):
	contestans = [int(x) for x in input().rstrip().split()]
	number = contestans[0]
	contestans = contestans[1:number + 1]
	formGroups(contestans)


from collections import Counter, defaultdict
from heapq import *
for _ in range(int(input())):
	k = sorted(list(map(int, input().split()[1:])))
	if not k:
		print(0)
		continue
	p = None
	f = False
	minplayers = 10 ** 9 + 1
	teams = defaultdict(list)
	for i in range(len(k)):
		if f and k[i] != p + 1:
			p = k[i]
		p = k[i]
		cur_team = (0, 0)
		if teams[p - 1]:
			cur_team = heappop(teams[p - 1])
		heappush(teams[p], (cur_team[0] + 1, cur_team[0] + 1))
		f = True
	for f in filter(None, teams.values()):
		minplayers = min(minplayers, f[0][0])
	print(minplayers)


t = int(input())
for z in range(t):
	contest = input().strip().split(' ')
	n = int(contest[0])
	if n == 0:
		print(0)
		continue
	cont = [int(x) for x in contest[1:]]
	cont.sort()
	current_chains_starts = [cont[0]]
	chain_count_filled = 1
	shortest_chain = len(cont)
	previous_contester = cont[0]
	for contester in cont[1:]:
		if contester == previous_contester + 1:
			while chain_count_filled < len(current_chains_starts):
				completed_chain_start = current_chains_starts.pop(0)
				chain_size = previous_contester - completed_chain_start
				shortest_chain = chain_size if shortest_chain > chain_size else shortest_chain
			chain_count_filled = 1
		elif contester == previous_contester:
			chain_count_filled += 1
			if chain_count_filled > len(current_chains_starts):
				current_chains_starts.append(contester)
		else:
			while chain_count_filled < len(current_chains_starts):
				completed_chain_start = current_chains_starts.pop(0)
				chain_size = previous_contester - completed_chain_start
				shortest_chain = chain_size if shortest_chain > chain_size else shortest_chain
			while len(current_chains_starts) > 0:
				completed_chain_start = current_chains_starts.pop(0)
				chain_size = previous_contester + 1 - completed_chain_start
				shortest_chain = chain_size if shortest_chain > chain_size else shortest_chain
			current_chains_starts.append(contester)
			chain_count_filled = 1
		previous_contester = contester
	while chain_count_filled < len(current_chains_starts):
		completed_chain_start = current_chains_starts.pop(0)
		chain_size = previous_contester - completed_chain_start
		shortest_chain = chain_size if shortest_chain > chain_size else shortest_chain
	while len(current_chains_starts) > 0:
		completed_chain_start = current_chains_starts.pop(0)
		chain_size = previous_contester + 1 - completed_chain_start
		shortest_chain = chain_size if shortest_chain > chain_size else shortest_chain
	print(shortest_chain)


import queue
for outer in range(int(input())):
	values = map(int, input().split()[1:])
	o = {}
	for v in values:
		o[v] = o[v] + 1 if v in o else 1
	values = sorted(o.items(), key=lambda x: x[0])
	smallest = len(values)
	lastValue = None
	qNew = queue.PriorityQueue()
	qLast = queue.PriorityQueue()
	for (value, quantity) in values:
		if lastValue != None and lastValue + 1 == value:
			while quantity > 0 and (not qLast.empty()):
				qNew.put(qLast.get() + 1)
				quantity -= 1
		if not qLast.empty():
			smallest = min(smallest, qLast.get())
			if smallest == 1:
				break
			qLast = queue.PriorityQueue()
		while quantity > 0:
			quantity -= 1
			qNew.put(1)
		lastValue = value
		(qLast, qNew) = (qNew, qLast)
	if not qLast.empty():
		smallest = min(smallest, qLast.get())
	print(smallest)


def grup(n, a, i):
	if i == n:
		return (None, 0)
	(mida, j) = (1, i + 1)
	cap = a[i]
	while j < n and a[j] == cap:
		mida += 1
		j += 1
	return (cap, mida)

def resol(n, a):
	if len(a) == 0:
		return 0
	millor = n
	llista = []
	(inici, coa) = (0, None)
	if a[-1] == 7:
		pass
	while inici < n:
		if coa == None:
			(coa, mida) = grup(n, a, inici)
			llista = [1] * mida
		else:
			ll = len(llista)
			(novacoa, mida) = grup(n, a, inici)
			if novacoa == coa + 1:
				coa = novacoa
				if mida < ll:
					millor = min(millor, min(llista[:ll - mida]))
					llista = llista[ll - mida:]
				elif mida > ll:
					llista += [0] * (mida - ll)
				llista = [x + 1 for x in llista]
			else:
				millor = min(millor, min(llista))
				coa = None
				inici -= mida
		inici += mida
	millor = min(millor, min(llista))
	return millor
t = int(input())
for tt in range(t):
	a = [int(x) for x in input().split()]
	n = a.pop(0)
	a.sort()
	print(resol(n, a))


def get_groups(A):
	last = A[0]
	groups = [[1]]
	for a in A[1:]:
		if a == last:
			groups[-1][-1] += 1
		elif a == last + 1:
			groups[-1].append(1)
		else:
			groups.append([1])
		last = a
	return groups

def get_sizes(counts):
	starts = []
	stops = []
	N = len(counts)
	counts = [0] + counts + [0]
	for i in range(1, N + 1):
		for k in range(max(0, counts[i] - counts[i - 1])):
			starts.append(i)
		for k in range(max(0, counts[i] - counts[i + 1])):
			stops.append(i + 1)
	sizes = [b - a for (a, b) in zip(starts, stops)]
	return sizes
T = int(input().strip())
for t in range(T):
	(n, *A) = (int(x) for x in input().strip().split())
	if n == 0:
		print(0)
	else:
		A.sort()
		print(min((min(get_sizes(g)) for g in get_groups(A))))


from collections import Counter, OrderedDict
t = int(input())
for _ in range(t):
	case = list(map(int, input().split()[1:]))
	try:
		smallest = min(case)
	except:
		print(0)
		continue
	case = list(map(lambda x: x + abs(smallest), case))
	counts = Counter(case)
	keys = OrderedDict.fromkeys(sorted(counts.keys()))
	groups = []
	while keys:
		current = 0
		deletable = set()
		first = True
		k = keys.keys()
		for key in k:
			if not first and (key - 1 not in k or counts[key - 1] >= counts[key]):
				break
			first = False
			counts[key] -= 1
			if not counts[key]:
				deletable.add(key)
			current += 1
		for key in deletable:
			keys.pop(key)
		groups.append(current)
	print(min(groups))


for _ in range(int(input())):
	a = list(map(int, input().split()))
	n = a.pop(0)
	assert n == len(a)
	if n == 0:
		print(0)
		continue
	a.sort()
	minteam = n
	teams = []
	lastv = a[0] - 2
	i = 0
	while i < n:
		v = a[i]
		c = 1
		while i + c < n and v == a[i + c]:
			c += 1
		assert v > lastv
		if v > lastv + 1:
			if len(teams) > 0:
				minteam = min(minteam, teams[0])
			teams = [1] * c
		elif c >= len(teams):
			teams = [1] * (c - len(teams)) + [t + 1 for t in teams]
		else:
			minteam = min(minteam, teams[c])
			teams = [t + 1 for t in teams[:c]]
		lastv = v
		i = i + c
	minteam = min(minteam, teams[0])
	print(minteam)


def main():
	for i in range(ut):
		skills = list(map(int, input().strip().split(' ')))
		print(extract(skills[1:]))

def extract(skills):
	distr = getDistribution(skills)
	keys = list(distr.keys())
	keys.sort()
	return getMinMaxLength(keys, distr)

def getDistribution(skills):
	distr = {}
	for skill in skills:
		crt = distr.get(skill, 0) + 1
		distr[skill] = crt
	return distr

def getMinMaxLength(keys, dic):
	minMax = len(keys)
	for key in keys:
		if not dic.get(key - 1):
			starts = []
		starts.append(getDiff(dic, key, key - 1))
		end = getDiff(dic, key, key + 1)
		if end:
			minMax = min(minMax, consume(starts, end))
			if minMax == 1:
				return minMax
	return minMax

def getDiff(distr, i, j):
	diff = distr.get(i, 0) - distr.get(j, 0)
	return diff if diff > 0 else 0

def consume(starts, ends):
	i = 0
	while starts[i] < ends:
		ends -= starts[i]
		starts[i] = 0
		i += 1
	starts[i] -= ends
	return len(starts) - i
ut = int(input().strip())
main()


from collections import defaultdict
for _ in range(int(input())):
	arr = list(map(int, input().split()))
	if arr == [0]:
		print(0)
		continue
	di = defaultdict(int)
	for i in arr[1:]:
		di[i] += 1
	arr = sorted(di)
	brr = []
	for i in arr:
		if i - 1 not in di:
			for j in range(di[i]):
				brr.append([i])
		elif di[i - 1] >= di[i]:
			for j in range(-di[i], 0):
				brr[j].append(i)
		else:
			for j in range(-di[i - 1], 0):
				brr[j].append(i)
			for j in range(di[i] - di[i - 1]):
				brr.append([i])
	print(min([len(i) for i in brr]))


from math import pow

def operate(A):
	S = set()
	val = -int(pow(10, 9) + 10)
	prevA = []
	nextA = []
	for i in range(len(A)):
		dd = A[i] - val
		if dd == 1:
			S.update(prevA)
			prevA = sorted(nextA, reverse=True)
			nextA = []
		elif dd > 1:
			S.update(nextA)
			prevA = []
			nextA = []
		if len(prevA) > 0:
			chainlength = prevA.pop()
			nextA.append(chainlength + 1)
		else:
			nextA.append(1)
		val = A[i]
	S.update(prevA)
	S.update(nextA)
	if len(S) > 0:
		return min(S)
	else:
		return 0
t = int(input())
while t > 0:
	A = [*map(int, input().rstrip().split(' '))]
	A = A[1:]
	A = sorted(A)
	print(operate(A))
	t -= 1


import sys

class Team:

	def __init__(self, start):
		self.start = start
		self.end = start

	def value(self):
		return self.end - self.start + 1

	def __repr__(self):
		return str(self.start) + ':' + str(self.end)
T = int(input().strip())
for a0 in range(T):
	A = list(map(int, input().strip().split(' ')))
	n = A.pop(0)
	if n == 0:
		print(0)
		continue
	A.sort(reverse=True)
	C = {}
	for i in A:
		if C.get(i, None) == None:
			t = Team(i)
			if C.get(i - 1, None) == None:
				C[i - 1] = [t]
			else:
				C[i - 1].append(t)
			if C.get(i + 1, None) == None:
				C[i + 1] = [t]
			else:
				C[i + 1].append(t)
		else:
			temp = min(C[i], key=lambda x: x.value())
			if temp.start - 1 == i:
				temp.start = i
				if C.get(i - 1, None) == None:
					C[i - 1] = []
				C[i].remove(temp)
				C[i - 1].append(temp)
				if len(C[i]) == 0:
					C[i] = None
			else:
				temp.end = i
				if C.get(i + 1, None) == None:
					C[i + 1] = []
				C[i].remove(temp)
				C[i + 1].append(temp)
				if len(C[i]) == 0:
					C[i] = None
	minm = n
	for item in C.keys():
		if C[item] != None and len(C[item]) > 0:
			temp = min(C[item], key=lambda x: x.value())
			if temp.value() < minm:
				minm = temp.value()
	print(minm)


from collections import Counter

def smallest_set(start, end, c):
	d = {}
	d[start - 1] = []
	for i in range(start, end + 1):
		d[i] = []
		prev_len = len(d[i - 1])
		new_lists = c[i] - prev_len
		if new_lists > 0:
			d[i] = [1] * new_lists
		if prev_len > 0:
			num_appends = min(prev_len, new_lists + prev_len)
			d[i - 1].sort()
			d[i] += [x + 1 for x in d[i - 1][:num_appends]]
			d[i - 1] = d[i - 1][num_appends:]
	ans = d[end][0]
	for i in range(start, end + 1):
		if len(d[i]) > 0:
			ans = min(ans, min(d[i]))
			if ans == 1:
				return 1
	return ans

def find_lowest_range(l, n):
	c = Counter(l)
	i = 0
	mini = n
	while i < len(l):
		end = i
		while end < n and (l[i] == l[end] or l[end] - l[end - 1] <= 1):
			end += 1
		end -= 1
		if end == i:
			return 1
		mini = min(mini, smallest_set(l[i], l[end], c))
		if mini == 1:
			return 1
		i = end + 1
	return mini
t = int(input())
for _ in range(t):
	l = list(map(int, input().split()))
	if l[0] == 0:
		print(0)
		continue
	n = l[0]
	l = sorted(l[1:])
	print(find_lowest_range(l, n))


from collections import Counter

def smallest_set(start, end, c):
	d = {}
	d[start - 1] = []
	for i in range(start, end + 1):
		d[i] = []
		prev_len = len(d[i - 1])
		new_lists = c[i] - prev_len
		if new_lists > 0:
			d[i] = [1] * new_lists
		if prev_len > 0:
			num_appends = min(prev_len, new_lists + prev_len)
			d[i - 1].sort()
			d[i] += [x + 1 for x in d[i - 1][:num_appends]]
			d[i - 1] = d[i - 1][num_appends:]
	ans = d[end][0]
	for i in range(start, end + 1):
		if len(d[i]) > 0:
			ans = min(ans, min(d[i]))
			if ans == 1:
				return 1
	return ans

def find_lowest_range(l, n):
	c = Counter(l)
	i = 0
	mini = n
	while i < len(l):
		end = i
		while end < n and (l[i] == l[end] or l[end] - l[end - 1] <= 1):
			end += 1
		end -= 1
		if end == i:
			return 1
		mini = min(mini, smallest_set(l[i], l[end], c))
		if mini == 1:
			return 1
		i = end + 1
	return mini
t = int(input())
for _ in range(t):
	l = list(map(int, input().split()))
	if l[0] == 0:
		print(0)
		continue
	n = l[0]
	l = sorted(l[1:])
	print(find_lowest_range(l, n))


from collections import Counter

def smallest_set(start, end, c):
	d = {}
	d[start - 1] = []
	for i in range(start, end + 1):
		d[i] = []
		prev_len = len(d[i - 1])
		new_lists = c[i] - prev_len
		if new_lists > 0:
			d[i] = [1] * new_lists
		if prev_len > 0:
			num_appends = min(prev_len, new_lists + prev_len)
			d[i - 1].sort()
			d[i] += [x + 1 for x in d[i - 1][:num_appends]]
			d[i - 1] = d[i - 1][num_appends:]
	ans = d[end][0]
	for i in range(start, end + 1):
		if len(d[i]) > 0:
			ans = min(ans, min(d[i]))
			if ans == 1:
				return 1
	return ans

def find_lowest_range(l, n):
	c = Counter(l)
	i = 0
	mini = n
	while i < len(l):
		end = i
		while end < n and (l[i] == l[end] or l[end] - l[end - 1] <= 1):
			end += 1
		end -= 1
		if end == i:
			return 1
		mini = min(mini, smallest_set(l[i], l[end], c))
		if mini == 1:
			return 1
		i = end + 1
	return mini
t = int(input())
for _ in range(t):
	l = list(map(int, input().split()))
	if l[0] == 0:
		print(0)
		continue
	n = l[0]
	l = sorted(l[1:])
	print(find_lowest_range(l, n))


from collections import Counter

def smallest_set(start, end, c):
	d = {}
	d[start - 1] = []
	for i in range(start, end + 1):
		d[i] = []
		prev_len = len(d[i - 1])
		new_lists = c[i] - prev_len
		if new_lists > 0:
			d[i] = [1] * new_lists
		if prev_len > 0:
			num_appends = min(prev_len, new_lists + prev_len)
			d[i - 1].sort()
			d[i] += [x + 1 for x in d[i - 1][:num_appends]]
			d[i - 1] = d[i - 1][num_appends:]
	ans = d[end][0]
	for i in range(start, end + 1):
		if len(d[i]) > 0:
			ans = min(ans, min(d[i]))
			if ans == 1:
				return 1
	return ans

def find_lowest_range(l, n):
	c = Counter(l)
	i = 0
	mini = n
	while i < len(l):
		end = i
		while end < n and (l[i] == l[end] or l[end] - l[end - 1] <= 1):
			end += 1
		end -= 1
		if end == i:
			return 1
		mini = min(mini, smallest_set(l[i], l[end], c))
		if mini == 1:
			return 1
		i = end + 1
	return mini
t = int(input())
for _ in range(t):
	l = list(map(int, input().split()))
	if l[0] == 0:
		print(0)
		continue
	n = l[0]
	l = sorted(l[1:])
	print(find_lowest_range(l, n))


from collections import Counter

def smallest_set(start, end, c):
	d = {}
	d[start - 1] = []
	for i in range(start, end + 1):
		d[i] = []
		prev_len = len(d[i - 1])
		new_lists = c[i] - prev_len
		if new_lists > 0:
			d[i] = [1] * new_lists
		if prev_len > 0:
			num_appends = min(prev_len, new_lists + prev_len)
			d[i - 1].sort()
			d[i] += [x + 1 for x in d[i - 1][:num_appends]]
			d[i - 1] = d[i - 1][num_appends:]
	ans = d[end][0]
	for i in range(start, end + 1):
		if len(d[i]) > 0:
			ans = min(ans, min(d[i]))
			if ans == 1:
				return 1
	return ans

def find_lowest_range(l, n):
	c = Counter(l)
	i = 0
	mini = n
	while i < len(l):
		end = i
		while end < n and (l[i] == l[end] or l[end] - l[end - 1] <= 1):
			end += 1
		end -= 1
		if end == i:
			return 1
		mini = min(mini, smallest_set(l[i], l[end], c))
		if mini == 1:
			return 1
		i = end + 1
	return mini
t = int(input())
for _ in range(t):
	l = list(map(int, input().split()))
	if l[0] == 0:
		print(0)
		continue
	n = l[0]
	l = sorted(l[1:])
	print(find_lowest_range(l, n))


from collections import Counter

def smallest_set(start, end, c):
	d = {}
	d[start - 1] = []
	for i in range(start, end + 1):
		d[i] = []
		prev_len = len(d[i - 1])
		new_lists = c[i] - prev_len
		if new_lists > 0:
			d[i] = [1] * new_lists
		if prev_len > 0:
			num_appends = min(prev_len, new_lists + prev_len)
			d[i - 1].sort()
			d[i] += [x + 1 for x in d[i - 1][:num_appends]]
			d[i - 1] = d[i - 1][num_appends:]
	ans = d[end][0]
	for i in range(start, end + 1):
		if len(d[i]) > 0:
			ans = min(ans, min(d[i]))
			if ans == 1:
				return 1
	return ans

def find_lowest_range(l, n):
	c = Counter(l)
	i = 0
	mini = n
	while i < len(l):
		end = i
		while end < n and (l[i] == l[end] or l[end] - l[end - 1] <= 1):
			end += 1
		end -= 1
		if end == i:
			return 1
		mini = min(mini, smallest_set(l[i], l[end], c))
		if mini == 1:
			return 1
		i = end + 1
	return mini
t = int(input())
for _ in range(t):
	l = list(map(int, input().split()))
	if l[0] == 0:
		print(0)
		continue
	n = l[0]
	l = sorted(l[1:])
	print(find_lowest_range(l, n))


def parseInt():
	return list(map(int, input().split()))
t = int(input())
for _ in range(t):
	arr = parseInt()[1:]
	n = len(arr)
	arr.sort()
	groups = []
	i = 0
	while i < n:
		if i == 0:
			groups.append((arr[i], 1))
			i += 1
		else:
			pos = len(groups) - 1
			if groups[pos][0] + 1 == arr[i]:
				groups[pos] = (arr[i], groups[pos][1] + 1)
				i += 1
			elif groups[pos][0] == arr[i]:
				val = arr[i]
				while i < n and val == arr[i]:
					pos -= 1
					if pos >= 0 and groups[pos][0] + 1 == arr[i]:
						groups[pos] = (arr[i], groups[pos][1] + 1)
					else:
						groups.append((arr[i], 1))
					i += 1
			else:
				groups.append((arr[i], 1))
				i += 1
	print(min((count for (last, count) in groups)) if groups else 0)


from collections import Counter

def smallest_set(start, end, c):
	d = {}
	d[start - 1] = []
	for i in range(start, end + 1):
		d[i] = []
		prev_len = len(d[i - 1])
		new_lists = c[i] - prev_len
		if new_lists > 0:
			d[i] = [1] * new_lists
		if prev_len > 0:
			num_appends = min(prev_len, new_lists + prev_len)
			d[i - 1].sort()
			d[i] += [x + 1 for x in d[i - 1][:num_appends]]
			d[i - 1] = d[i - 1][num_appends:]
	ans = d[end][0]
	for i in range(start, end + 1):
		if len(d[i]) > 0:
			ans = min(ans, min(d[i]))
			if ans == 1:
				return 1
	return ans

def find_lowest_range(l, n):
	c = Counter(l)
	i = 0
	mini = n
	while i < len(l):
		end = i
		while end < n and (l[i] == l[end] or l[end] - l[end - 1] <= 1):
			end += 1
		end -= 1
		if end == i:
			return 1
		mini = min(mini, smallest_set(l[i], l[end], c))
		if mini == 1:
			return 1
		i = end + 1
	return mini
t = int(input())
for _ in range(t):
	l = list(map(int, input().split()))
	if l[0] == 0:
		print(0)
		continue
	n = l[0]
	l = sorted(l[1:])
	print(find_lowest_range(l, n))


from collections import Counter

def smallest_set(start, end, c):
	d = {}
	d[start - 1] = []
	for i in range(start, end + 1):
		d[i] = []
		prev_len = len(d[i - 1])
		new_lists = c[i] - prev_len
		if new_lists > 0:
			d[i] = [1] * new_lists
		if prev_len > 0:
			num_appends = min(prev_len, new_lists + prev_len)
			d[i - 1].sort()
			d[i] += [x + 1 for x in d[i - 1][:num_appends]]
			d[i - 1] = d[i - 1][num_appends:]
	ans = d[end][0]
	for i in range(start, end + 1):
		if len(d[i]) > 0:
			ans = min(ans, min(d[i]))
			if ans == 1:
				return 1
	return ans

def find_lowest_range(l, n):
	c = Counter(l)
	i = 0
	mini = n
	while i < len(l):
		end = i
		while end < n and (l[i] == l[end] or l[end] - l[end - 1] <= 1):
			end += 1
		end -= 1
		if end == i:
			return 1
		mini = min(mini, smallest_set(l[i], l[end], c))
		if mini == 1:
			return 1
		i = end + 1
	return mini
t = int(input())
for _ in range(t):
	l = list(map(int, input().split()))
	if l[0] == 0:
		print(0)
		continue
	n = l[0]
	l = sorted(l[1:])
	print(find_lowest_range(l, n))


def agregarAlMinimoPosible(matrix, elem, n, rep):
	m = len(matrix)
	if m - 2 - rep >= 0 and elem - matrix[m - 2 - rep][len(matrix[m - 2 - rep]) - 1] == 1:
		matrix[m - 2 - rep].append(elem)
	else:
		matrix.append([elem])

def calculateMinimum(matrix, n):
	minimum = n
	for i in range(len(matrix)):
		if len(matrix[i]) < minimum:
			minimum = len(matrix[i])
	return minimum
tests = int(input())
for test in range(tests):
	arr = [int(s) for s in input().split()]
	n = arr[0]
	arr = arr[1:n + 1]
	arr = sorted(arr)
	matrix = []
	rep = 0
	suc = 0
	for i in range(n):
		if i == 0:
			matrix.append([arr[i]])
		if i > 0:
			if arr[i] - arr[i - 1] > 1:
				rep = 0
				suc = 0
				matrix.append([arr[i]])
			if arr[i] == arr[i - 1]:
				agregarAlMinimoPosible(matrix, arr[i], n, rep)
				if suc == 1:
					rep += 1
			if arr[i] - arr[i - 1] == 1:
				suc += 1
				if suc > 1:
					rep = 0
					suc = 1
				matrix[len(matrix) - 1].append(arr[i])
	minimum = n
	for i in range(len(matrix)):
		if len(matrix[i]) < minimum:
			minimum = len(matrix[i])
	print(minimum)


from collections import Counter

def smallest_set(start, end, c):
	d = {}
	d[start - 1] = []
	for i in range(start, end + 1):
		d[i] = []
		prev_len = len(d[i - 1])
		new_lists = c[i] - prev_len
		if new_lists > 0:
			d[i] = [1] * new_lists
		if prev_len > 0:
			num_appends = min(prev_len, new_lists + prev_len)
			d[i - 1].sort()
			d[i] += [x + 1 for x in d[i - 1][:num_appends]]
			d[i - 1] = d[i - 1][num_appends:]
	ans = d[end][0]
	for i in range(start, end + 1):
		if len(d[i]) > 0:
			ans = min(ans, min(d[i]))
			if ans == 1:
				return 1
	return ans

def find_lowest_range(l, n):
	c = Counter(l)
	i = 0
	mini = n
	while i < len(l):
		end = i
		while end < n and (l[i] == l[end] or l[end] - l[end - 1] <= 1):
			end += 1
		end -= 1
		if end == i:
			return 1
		mini = min(mini, smallest_set(l[i], l[end], c))
		if mini == 1:
			return 1
		i = end + 1
	return mini
t = int(input())
for _ in range(t):
	l = list(map(int, input().split()))
	if l[0] == 0:
		print(0)
		continue
	n = l[0]
	l = sorted(l[1:])
	print(find_lowest_range(l, n))


from collections import Counter

def smallest_set(start, end, c):
	d = {}
	d[start - 1] = []
	for i in range(start, end + 1):
		d[i] = []
		prev_len = len(d[i - 1])
		new_lists = c[i] - prev_len
		if new_lists > 0:
			d[i] = [1] * new_lists
		if prev_len > 0:
			num_appends = min(prev_len, new_lists + prev_len)
			d[i - 1].sort()
			d[i] += [x + 1 for x in d[i - 1][:num_appends]]
			d[i - 1] = d[i - 1][num_appends:]
	ans = d[end][0]
	for i in range(start, end + 1):
		if len(d[i]) > 0:
			ans = min(ans, min(d[i]))
			if ans == 1:
				return 1
	return ans

def find_lowest_range(l, n):
	c = Counter(l)
	i = 0
	mini = n
	while i < len(l):
		end = i
		while end < n and (l[i] == l[end] or l[end] - l[end - 1] <= 1):
			end += 1
		end -= 1
		if end == i:
			return 1
		mini = min(mini, smallest_set(l[i], l[end], c))
		if mini == 1:
			return 1
		i = end + 1
	return mini
t = int(input())
for _ in range(t):
	l = list(map(int, input().split()))
	if l[0] == 0:
		print(0)
		continue
	n = l[0]
	l = sorted(l[1:])
	print(find_lowest_range(l, n))


from collections import Counter

def smallest_set(start, end, c):
	d = {}
	d[start - 1] = []
	for i in range(start, end + 1):
		d[i] = []
		prev_len = len(d[i - 1])
		new_lists = c[i] - prev_len
		if new_lists > 0:
			d[i] = [1] * new_lists
		if prev_len > 0:
			num_appends = min(prev_len, new_lists + prev_len)
			d[i - 1].sort()
			d[i] += [x + 1 for x in d[i - 1][:num_appends]]
			d[i - 1] = d[i - 1][num_appends:]
	ans = d[end][0]
	for i in range(start, end + 1):
		if len(d[i]) > 0:
			ans = min(ans, min(d[i]))
			if ans == 1:
				return 1
	return ans

def find_lowest_range(l, n):
	c = Counter(l)
	i = 0
	mini = n
	while i < len(l):
		end = i
		while end < n and (l[i] == l[end] or l[end] - l[end - 1] <= 1):
			end += 1
		end -= 1
		if end == i:
			return 1
		mini = min(mini, smallest_set(l[i], l[end], c))
		if mini == 1:
			return 1
		i = end + 1
	return mini
t = int(input())
for _ in range(t):
	l = list(map(int, input().split()))
	if l[0] == 0:
		print(0)
		continue
	n = l[0]
	l = sorted(l[1:])
	print(find_lowest_range(l, n))


from collections import Counter

def smallest_set(start, end, c):
	d = {}
	d[start - 1] = []
	for i in range(start, end + 1):
		d[i] = []
		prev_len = len(d[i - 1])
		new_lists = c[i] - prev_len
		if new_lists > 0:
			d[i] = [1] * new_lists
		if prev_len > 0:
			num_appends = min(prev_len, new_lists + prev_len)
			d[i - 1].sort()
			d[i] += [x + 1 for x in d[i - 1][:num_appends]]
			d[i - 1] = d[i - 1][num_appends:]
	ans = d[end][0]
	for i in range(start, end + 1):
		if len(d[i]) > 0:
			ans = min(ans, min(d[i]))
			if ans == 1:
				return 1
	return ans

def find_lowest_range(l, n):
	c = Counter(l)
	i = 0
	mini = n
	while i < len(l):
		end = i
		while end < n and (l[i] == l[end] or l[end] - l[end - 1] <= 1):
			end += 1
		end -= 1
		if end == i:
			return 1
		mini = min(mini, smallest_set(l[i], l[end], c))
		if mini == 1:
			return 1
		i = end + 1
	return mini
t = int(input())
for _ in range(t):
	l = list(map(int, input().split()))
	if l[0] == 0:
		print(0)
		continue
	n = l[0]
	l = sorted(l[1:])
	print(find_lowest_range(l, n))


class Solution:

	def __init__(self):
		self.starts = []
		self.min = 2000000000
		self.lastScore = -2000000000
		self.currentScore = -2000000000
		self.currentCount = 0

	def removeRange(self, end):
		if end <= 0:
			return
		team_count = self.lastScore - self.starts[end - 1] + 1
		if team_count < self.min:
			self.min = team_count
		del self.starts[0:end]

	def finalize(self):
		self.handleScores(self.currentScore, self.currentCount)
		self.removeRange(len(self.starts))

	def handleScore(self, score):
		if score != self.currentScore:
			if self.currentCount != 0:
				self.handleScores(self.currentScore, self.currentCount)
			self.currentCount = 1
			self.currentScore = score
		else:
			self.currentCount = self.currentCount + 1

	def handleScores(self, score, count):
		if score != self.lastScore + 1:
			if len(self.starts) > 0:
				self.removeRange(len(self.starts))
			for i in range(count):
				self.starts.append(score)
		elif count < len(self.starts):
			self.removeRange(len(self.starts) - count)
		elif count > len(self.starts):
			for i in range(count - len(self.starts)):
				self.starts.append(score)
		self.lastScore = score

def solve(scores):
	scores.sort()
	solution = Solution()
	for i in range(len(scores)):
		solution.handleScore(scores[i])
	solution.finalize()
	print(solution.min)

def doProblem():
	numbers = list(map(int, input().strip().split(' ')))
	n = numbers[0]
	del numbers[0]
	if n == 0:
		print(0)
	else:
		solve(numbers)
N = int(input())
if N == 0:
	print(0)
else:
	for i in range(N):
		doProblem()


def min_team(contestants):
	if len(contestants) == 1:
		return 1
	teams = []
	last_skill = contestants[0]
	min_size = 1
	live_teams = []
	next_teams = [[contestants[0]]]
	for i in range(1, len(contestants)):
		if contestants[i] == last_skill:
			if live_teams == []:
				next_teams.append([contestants[i]])
			else:
				next_teams.append(live_teams.pop(0))
				next_teams[-1].append(contestants[i])
		else:
			teams += live_teams
			live_teams = sorted(next_teams, key=len)
			next_teams = [live_teams.pop(0)]
			next_teams[0].append(contestants[i])
			last_skill = contestants[i]
	teams += live_teams
	teams += next_teams
	return min(map(lambda x: len(x), teams))

def solve(skills):
	if skills == []:
		return 0
	sub_sets = []
	curr_set = [skills[0]]
	i = 0
	while i < n - 1:
		if skills[i + 1] > skills[i] + 1:
			sub_sets.append(curr_set)
			curr_set = [skills[i + 1]]
			i += 1
		else:
			curr_set.append(skills[i + 1])
			i += 1
	sub_sets.append(curr_set)
	return sub_sets
for t in range(int(input())):
	skills = list(map(int, input().split()))
	n = skills.pop(0)
	skills = sorted(skills)
	solved_skills = solve(skills)
	if solved_skills == 0:
		print(0)
	else:
		mins = map(lambda x: min_team(x), solved_skills)
		print(min(mins))


from collections import Counter, OrderedDict

class OrderedCounter(Counter, OrderedDict):

	def __repr__(self):
		return '%s(%r)' % (self.__class__.__name__, OrderedDict(self))

	def __reduce__(self):
		return (self.__class__, (OrderedDict(self),))

def gen_sequential_sets(oc):
	(curr, prev) = (None, None)
	lst = []
	tbd = []
	for v in oc:
		if oc[v] == 0:
			tbd.append(v)
			continue
		curr = v
		if prev is None or (curr - prev == 1 and oc[curr] > oc[prev]):
			prev = curr
			oc[curr] -= 1
			lst.append(curr)
		if curr - prev > 1:
			break
	for elem in tbd:
		del oc[elem]
	return lst

def smallest_size(a):
	oc = OrderedCounter()
	for elem in sorted(a):
		oc[elem] += 1
	curr_size = float('Inf')
	while True:
		s = gen_sequential_sets(oc)
		if not s:
			break
		if len(s) < curr_size:
			curr_size = len(s)
	return curr_size
t = int(input())
for case in range(t):
	ary = [int(x) for x in input().strip().split(' ')]
	if ary[0] == 0:
		print('0')
	else:
		ary = ary[1:]
		print(smallest_size(ary))


import heapq
from collections import defaultdict

def construct_teams(member_heap):
	teams = defaultdict(list)
	team_nr = 0
	while member_heap:
		member = -heapq.heappop(member_heap)
		if member + 1 in teams:
			stats = heapq.heappop(teams[member + 1])
			if len(teams[member + 1]) == 0:
				del teams[member + 1]
			heapq.heappush(teams[member], (stats[0] + 1, stats[1]))
		else:
			heapq.heappush(teams[member], (1, team_nr))
			team_nr += 1
	min_team_sizes = [heapq.heappop(teams[member])[0] for member in teams]
	return min(min_team_sizes)
num_cases = int(input().strip())
for _ in range(num_cases):
	vals = input().strip().split(' ')
	if int(vals[0]) == 0:
		print(0)
	else:
		member_heap = [-int(vals[el]) for el in range(1, len(vals))]
		heapq.heapify(member_heap)
		print(construct_teams(member_heap))


from collections import Counter

def smallest_set(start, end, c):
	d = {}
	d[start - 1] = []
	for i in range(start, end + 1):
		d[i] = []
		prev_len = len(d[i - 1])
		new_lists = c[i] - prev_len
		if new_lists > 0:
			d[i] = [1] * new_lists
		if prev_len > 0:
			num_appends = min(prev_len, new_lists + prev_len)
			d[i - 1].sort()
			d[i] += [x + 1 for x in d[i - 1][:num_appends]]
			d[i - 1] = d[i - 1][num_appends:]
	ans = d[end][0]
	for i in range(start, end + 1):
		if len(d[i]) > 0:
			ans = min(ans, min(d[i]))
			if ans == 1:
				return 1
	return ans

def find_lowest_range(l, n):
	c = Counter(l)
	i = 0
	mini = n
	while i < len(l):
		end = i
		while end < n and (l[i] == l[end] or l[end] - l[end - 1] <= 1):
			end += 1
		end -= 1
		if end == i:
			return 1
		mini = min(mini, smallest_set(l[i], l[end], c))
		if mini == 1:
			return 1
		i = end + 1
	return mini
t = int(input())
for _ in range(t):
	l = list(map(int, input().split()))
	if l[0] == 0:
		print(0)
		continue
	n = l[0]
	l = sorted(l[1:])
	print(find_lowest_range(l, n))


def increaseAll(a, increment):
	for i in range(len(a)):
		a[i] += increment

def findMaxMinGroup(a):
	a.sort()
	nums = {}
	for num in a:
		if num in nums:
			nums[num] += 1
		else:
			nums[num] = 1
	previousNum = a[0]
	shortestLen = 10 ** 10
	threadLengths = [1 for _ in range(nums[a[0]])]
	for num in sorted(nums.keys())[1:]:
		if num - previousNum != 1:
			if shortestLen > threadLengths[-1]:
				shortestLen = threadLengths[-1]
			threadLengths = [1 for _ in range(nums[num])]
		elif nums[num] == nums[previousNum]:
			increaseAll(threadLengths, 1)
		elif nums[num] > nums[previousNum]:
			increaseAll(threadLengths, 1)
			for _ in range(nums[previousNum], nums[num]):
				threadLengths.append(1)
		elif nums[num] < nums[previousNum]:
			for _ in range(nums[num], nums[previousNum]):
				if threadLengths[0] < shortestLen:
					shortestLen = threadLengths[0]
				threadLengths.pop(0)
			increaseAll(threadLengths, 1)
		previousNum = num
	if threadLengths[-1] < shortestLen:
		shortestLen = threadLengths[-1]
	return shortestLen
n = int(input().strip())
for i in range(n):
	a = list(map(int, input().strip().split(' ')))
	if len(a) == 1:
		print(0)
		continue
	a.pop(0)
	print(findMaxMinGroup(a))


from collections import Counter

def smallest_set(start, end, c):
	d = {}
	d[start - 1] = []
	for i in range(start, end + 1):
		d[i] = []
		prev_len = len(d[i - 1])
		new_lists = c[i] - prev_len
		if new_lists > 0:
			d[i] = [1] * new_lists
		if prev_len > 0:
			num_appends = min(prev_len, new_lists + prev_len)
			d[i - 1].sort()
			d[i] += [x + 1 for x in d[i - 1][:num_appends]]
			d[i - 1] = d[i - 1][num_appends:]
	ans = d[end][0]
	for i in range(start, end + 1):
		if len(d[i]) > 0:
			ans = min(ans, min(d[i]))
			if ans == 1:
				return 1
	return ans

def find_lowest_range(l, n):
	c = Counter(l)
	i = 0
	mini = n
	while i < len(l):
		end = i
		while end < n and (l[i] == l[end] or l[end] - l[end - 1] <= 1):
			end += 1
		end -= 1
		if end == i:
			return 1
		mini = min(mini, smallest_set(l[i], l[end], c))
		if mini == 1:
			return 1
		i = end + 1
	return mini
t = int(input())
for _ in range(t):
	l = list(map(int, input().split()))
	if l[0] == 0:
		print(0)
		continue
	n = l[0]
	l = sorted(l[1:])
	print(find_lowest_range(l, n))


import bisect as bi

def get_skill_count(skills: list, searched_skill_index: int) -> int:
	count = 1
	searched_skill = skills[searched_skill_index]
	for i in range(searched_skill_index + 1, len(skills)):
		if skills[i] != searched_skill:
			break
		count += 1
	return count

def calculate_same_skills_groups(skills: list) -> list:
	result = []
	skills.sort()
	prev_skill = skills[0]
	prev_skill_count = get_skill_count(skills, 0)
	sequential_skills_group = []
	sequential_skills_group.append(get_skill_count(skills, 0))
	skill_index = prev_skill_count
	while skill_index < len(skills):
		if prev_skill + 1 != skills[skill_index]:
			result.append(sequential_skills_group)
			sequential_skills_group = []
		same_skills_count = get_skill_count(skills, skill_index)
		sequential_skills_group.append(same_skills_count)
		prev_skill = skills[skill_index]
		skill_index += same_skills_count
	result.append(sequential_skills_group)
	return result

def find_peak(group, start_index):
	prev_element = group[start_index]
	for i in range(start_index + 1, len(group)):
		cur_element = group[i]
		if prev_element > cur_element:
			return i - 1
		prev_element = cur_element
	return len(group) - 1

def get_last_equal_elements_count(group):
	last_elem = group[-1]
	for i in range(len(group) - 2, -1, -1):
		if last_elem == group[i]:
			continue
		return len(group) - 1 - i
	return len(group)

def sub_from_group(group, start_index, end_index, delta):
	non_zero_index = start_index
	for i in range(start_index, end_index):
		group[i] -= delta
		if group[i] == 0:
			non_zero_index = i
	return non_zero_index + 1

def find_non_zero_position(group, start_index):
	for i in range(start_index, len(group)):
		if group[i] != 0:
			return i
	return len(group)

def calc_max_team_size_of_skill_group(group: list) -> int:
	if len(group) == 1:
		return 1
	max_team_size = len(group)
	skill_index = 0
	peak_index = 0
	while skill_index < len(group) - 1:
		peak_index = find_peak(group, max(peak_index, skill_index))
		if peak_index == len(group) - 1:
			last_eq_elements_count = get_last_equal_elements_count(group)
			max_team_size = min(max_team_size, last_eq_elements_count)
			break
		delta = group[peak_index] - group[peak_index + 1]
		delta_index = bi.bisect_left(group, delta, skill_index, peak_index)
		delta_actual = delta_actual = group[delta_index]
		max_team_size = min(max_team_size, peak_index + 1 - delta_index)
		sub = group[peak_index] - delta_actual
		i = peak_index + 1
		prev_value = group[i]
		while i < len(group) and prev_value >= group[i] and (group[i] >= sub):
			prev_value = group[i]
			group[i] = sub
			i += 1
		skill_index = sub_from_group(group, delta_index, peak_index + 1, delta_actual)
		if i > peak_index + 1:
			max_delta = prev_value - sub
			for j in range(i, len(group)):
				if group[j] <= sub:
					break
				group[j] = max(group[j] - max_delta, sub)
				sub = max(sub, group[j])
		peak_index = i - 1
		skill_index = find_non_zero_position(group, skill_index)
	return max_team_size

def calculate_max_team_size(skills: list) -> int:
	if not skills:
		return 0
	max_team_size = len(skills)
	skill_groups = calculate_same_skills_groups(skills)
	for skill_group in skill_groups:
		max_team_size = min(max_team_size, calc_max_team_size_of_skill_group(skill_group))
		if max_team_size == 1:
			break
	return max_team_size
test_cases_count = int(input())
for _ in range(0, test_cases_count):
	skills = list(map(int, input().split()))
	skills = skills[1:]
	print(calculate_max_team_size(skills))


import heapq
from heapq import heappush, heappop

class Team:

	def __init__(self, id, skillLevel):
		self.id = id
		self.size = 1
		self.minLevel = skillLevel
		self.maxLevel = skillLevel

	def add(self, skillLevel):
		self.minLevel = min(self.minLevel, skillLevel)
		self.maxLevel = max(self.maxLevel, skillLevel)
		self.size += 1

	def canAdd(self, skillLevel):
		b = False
		overridden = None
		if skillLevel == self.maxLevel + 1:
			b = True
			overridden = self.maxLevel
		if skillLevel == self.minLevel - 1:
			b = True
			overridden = self.minLevel
		return (b, overridden)

	def __cmp__(self, other):
		return cmp(self.size, other.size)

	def __le__(self, other):
		return self.size <= other.size

	def __eq__(self, other):
		return self.size == other.size

	def __lt__(self, other):
		return self.size < other.size

	def __hash__(self):
		return int(self.id)

	def __repr__(self):
		return 'Team {}: ({},{}), size: {}'.format(self.id, self.minLevel, self.maxLevel, self.size)

def splitTeams(skillLevels):
	teams = []
	maxLevel = {}
	minLevel = {}
	id = 0
	for skill in skillLevels:
		possibleTeams = []
		if skill - 1 in maxLevel:
			possibleTeams += maxLevel[skill - 1]
		if skill + 1 in minLevel:
			possibleTeams += minLevel[skill - 1]
		heapq.heapify(possibleTeams)
		if len(possibleTeams) == 0:
			newTeam = Team(id, skill)
			id += 1
			teams.append(newTeam)
			if skill in minLevel:
				heappush(minLevel[skill], newTeam)
			else:
				lst = [(1, newTeam)]
				heapq.heapify(lst)
				minLevel[skill] = [newTeam]
			if skill in maxLevel:
				heappush(maxLevel[skill], newTeam)
			else:
				lst = [newTeam]
				heapq.heapify(lst)
				maxLevel[skill] = [newTeam]
			continue
		smallestTeam = heappop(possibleTeams)
		(canAdd, overridden) = smallestTeam.canAdd(skill)
		while not canAdd:
			if len(possibleTeams) == 0:
				newTeam = Team(id, skill)
				id += 1
				teams.append(newTeam)
				if skill in minLevel:
					heappush(minLevel[skill], newTeam)
				else:
					lst = [(1, newTeam)]
					heapq.heapify(lst)
					minLevel[skill] = [newTeam]
				if skill in maxLevel:
					heappush(maxLevel[skill], newTeam)
				else:
					lst = [newTeam]
					heapq.heapify(lst)
					maxLevel[skill] = [newTeam]
				break
			smallestTeam = heappop(possibleTeams)
			(canAdd, overridden) = smallestTeam.canAdd(skill)
		if not canAdd:
			continue
		smallestTeam.add(skill)
		if overridden < skill:
			if skill in maxLevel:
				heappush(maxLevel[skill], smallestTeam)
			else:
				lst = [smallestTeam]
				heapq.heapify(lst)
				maxLevel[skill] = [smallestTeam]
		elif skill in minLevel:
			heappush(minLevel[skill], smallestTeam)
		else:
			lst = [smallestTeam]
			heapq.heapify(lst)
			minLevel[skill] = [smallestTeam]
	return min(teams, key=lambda team: team.size).size
testCases = int(input().strip())
for test in range(testCases):
	values = list(map(int, input().strip().split(' ')))
	if values[0] == 0:
		print(0)
		continue
	skillLevels = sorted(values[1:])
	print(splitTeams(skillLevels))


from collections import Counter
from queue import Queue

def submain() -> int:
	m = dict(Counter(list(map(int, input().strip().split(' ')))[1:]))
	arr = sorted(m.keys())
	q = Queue()
	if len(arr) == 0:
		return 0
	if len(arr) == 1:
		return 1
	for x in [arr[0]] * m[arr[0]]:
		q.put(x)
	last = arr[0]
	min_length = 10000000000000000000000000000000000
	for x in arr[1:]:
		h = 0 if x != last + 1 else m[x]
		while q.qsize() > h:
			y = q.get()
			if last - y + 1 < min_length:
				min_length = last - y + 1
		h = m[x]
		while q.qsize() < h:
			q.put(x)
		last = x
	while q.qsize() > 0:
		y = q.get()
		if last - y + 1 < min_length:
			min_length = last - y + 1
	return min_length
n = int(input())
for i in range(n):
	print(submain())


from collections import Counter

def smallest_set(start, end, c):
	d = {}
	d[start - 1] = []
	for i in range(start, end + 1):
		d[i] = []
		prev_len = len(d[i - 1])
		new_lists = c[i] - prev_len
		if new_lists > 0:
			d[i] = [1] * new_lists
		if prev_len > 0:
			num_appends = min(prev_len, new_lists + prev_len)
			d[i - 1].sort()
			d[i] += [x + 1 for x in d[i - 1][:num_appends]]
			d[i - 1] = d[i - 1][num_appends:]
	ans = d[end][0]
	for i in range(start, end + 1):
		if len(d[i]) > 0:
			ans = min(ans, min(d[i]))
			if ans == 1:
				return 1
	return ans

def find_lowest_range(l, n):
	c = Counter(l)
	i = 0
	mini = n
	while i < len(l):
		end = i
		while end < n and (l[i] == l[end] or l[end] - l[end - 1] <= 1):
			end += 1
		end -= 1
		if end == i:
			return 1
		mini = min(mini, smallest_set(l[i], l[end], c))
		if mini == 1:
			return 1
		i = end + 1
	return mini
t = int(input())
for _ in range(t):
	l = list(map(int, input().split()))
	if l[0] == 0:
		print(0)
		continue
	n = l[0]
	l = sorted(l[1:])
	print(find_lowest_range(l, n))


from heapq import heappush, heappop

def push(table, index, value):
	if index not in table:
		table[index] = []
	heappush(table[index], value)

def pop(table, index):
	el = heappop(table[index])
	return (el[0], el[1])
T = int(input())
for t in range(T):
	line = list(map(int, input().strip().split()))
	(N, arr) = (line[0], line[1:])
	if N == 0:
		print(0)
		continue
	arr = sorted(arr)
	sizes = []
	last = {}
	for v in arr:
		if v - 1 in last and len(last[v - 1]) > 0:
			(size, index) = pop(last, v - 1)
			sizes[index] += 1
			push(last, v, (size + 1, index))
		else:
			push(last, v, (1, len(sizes)))
			sizes.append(1)
	print(min(sizes))


from collections import Counter

def smallest_set(start, end, c):
	d = {}
	d[start - 1] = []
	for i in range(start, end + 1):
		d[i] = []
		prev_len = len(d[i - 1])
		new_lists = c[i] - prev_len
		if new_lists > 0:
			d[i] = [1] * new_lists
		if prev_len > 0:
			num_appends = min(prev_len, new_lists + prev_len)
			d[i - 1].sort()
			d[i] += [x + 1 for x in d[i - 1][:num_appends]]
			d[i - 1] = d[i - 1][num_appends:]
	ans = d[end][0]
	for i in range(start, end + 1):
		if len(d[i]) > 0:
			ans = min(ans, min(d[i]))
			if ans == 1:
				return 1
	return ans

def find_lowest_range(l, n):
	c = Counter(l)
	i = 0
	mini = n
	while i < len(l):
		end = i
		while end < n and (l[i] == l[end] or l[end] - l[end - 1] <= 1):
			end += 1
		end -= 1
		if end == i:
			return 1
		mini = min(mini, smallest_set(l[i], l[end], c))
		if mini == 1:
			return 1
		i = end + 1
	return mini
t = int(input())
for _ in range(t):
	l = list(map(int, input().split()))
	if l[0] == 0:
		print(0)
		continue
	n = l[0]
	l = sorted(l[1:])
	print(find_lowest_range(l, n))


def minspan(span):
	if len(span) == 1:
		return 1
	for i in range(1, len(span) - 1):
		if span[i] > span[i - 1] + span[i + 1]:
			return 1
	c = span[:]
	n = len(span)
	i = 0
	m = 999999999
	while i < n:
		while i < n and c[i] == 0:
			i = i + 1
		if i >= n:
			return m
		d = 1
		c[i] = c[i] - d
		j = i + 1
		mm = 1
		while j < n and span[j] >= span[j - 1]:
			c[j] = c[j] - d
			if c[j] == 0 and c[i] == 0:
				i = j
			j = j + 1
			mm = mm + 1
		span = c[:]
		m = min(mm, m)
	return m

def solve(inp):
	n = inp[0]
	if n == 0:
		return 0
	a = sorted(inp[1:])
	seg = []
	g = [a[0]]
	for i in range(1, n):
		if a[i] <= a[i - 1] + 1:
			g.append(a[i])
		else:
			seg.append(g[:])
			g = [a[i]]
	seg.append(g)
	h = []
	for i in range(len(seg)):
		d = seg[i][0]
		for j in range(len(seg[i])):
			seg[i][j] = seg[i][j] - d
			if j == len(seg[i]) - 1:
				h.append([0] * (seg[i][j] + 1))
	for i in range(len(seg)):
		d = seg[i][0]
		for j in range(len(seg[i])):
			h[i][seg[i][j]] = h[i][seg[i][j]] + 1
	m = minspan(h[0])
	for i in range(1, len(h)):
		m = min(minspan(h[i]), m)
	return m
t = int(input())
for i in range(t):
	print(solve([int(x) for x in input().split()]))


from collections import Counter

def smallest_set(start, end, c):
	d = {}
	d[start - 1] = []
	for i in range(start, end + 1):
		d[i] = []
		prev_len = len(d[i - 1])
		new_lists = c[i] - prev_len
		if new_lists > 0:
			d[i] = [1] * new_lists
		if prev_len > 0:
			num_appends = min(prev_len, new_lists + prev_len)
			d[i - 1].sort()
			d[i] += [x + 1 for x in d[i - 1][:num_appends]]
			d[i - 1] = d[i - 1][num_appends:]
	ans = d[end][0]
	for i in range(start, end + 1):
		if len(d[i]) > 0:
			ans = min(ans, min(d[i]))
			if ans == 1:
				return 1
	return ans

def find_lowest_range(l, n):
	c = Counter(l)
	i = 0
	mini = n
	while i < len(l):
		end = i
		while end < n and (l[i] == l[end] or l[end] - l[end - 1] <= 1):
			end += 1
		end -= 1
		if end == i:
			return 1
		mini = min(mini, smallest_set(l[i], l[end], c))
		if mini == 1:
			return 1
		i = end + 1
	return mini
t = int(input())
for _ in range(t):
	l = list(map(int, input().split()))
	if l[0] == 0:
		print(0)
		continue
	n = l[0]
	l = sorted(l[1:])
	print(find_lowest_range(l, n))


from collections import defaultdict
t = int(input())

class SortedBag:

	def __init__(self):
		self.inner = []

	def insert(self, item, num):
		self.inner.append([item, num])

	def pop_n(self, n):
		(to_pop, to_pop_count) = self.inner[0]
		while n > 0:
			(to_pop, to_pop_count) = self.inner[0]
			if to_pop_count >= n:
				self.inner[0][1] -= n
			if to_pop_count <= n:
				self.inner.pop(0)
			n -= to_pop_count
		return to_pop

	def peek_last(self):
		return self.inner[-1][0]

	def empty(self):
		return not self.inner
for _ in range(t):
	inp = list(map(int, input().rstrip().split()))
	n = inp[0]
	ar = inp[1:]
	if n == 1:
		print(1)
		continue
	if n == 0:
		print(0)
		continue
	count_by_skill = defaultdict(int)
	for i in ar:
		count_by_skill[i] += 1
	keys = sorted(count_by_skill.keys())
	min_size = 100000
	run_starts = SortedBag()
	run_starts.insert(keys[0], count_by_skill[keys[0]])
	for i in range(len(keys) - 1):
		curr_skill = keys[i]
		next_skill = keys[i + 1]
		num_curr_skill = count_by_skill[keys[i]]
		num_next_skill = count_by_skill[keys[i + 1]]
		if curr_skill + 1 != next_skill:
			if not run_starts.empty():
				min_size = min(min_size, curr_skill - run_starts.peek_last() + 1)
			else:
				min_size = 1
				break
			run_starts = SortedBag()
			run_starts.insert(next_skill, num_next_skill)
		else:
			if num_curr_skill > num_next_skill:
				num_finished_runs = num_curr_skill - num_next_skill
				finished_runs = run_starts.pop_n(num_finished_runs)
				min_size = min(min_size, curr_skill - finished_runs + 1)
			if num_curr_skill < num_next_skill:
				num_new_runs = num_next_skill - num_curr_skill
				run_starts.insert(next_skill, num_new_runs)
	if not run_starts.empty():
		if run_starts.peek_last() == keys[-1]:
			min_size = 1
		else:
			min_size = min(min_size, keys[-1] - run_starts.peek_last() + 1)
	print(min_size)


from collections import Counter

def find_min(m, start, end, diff, freq):
	if diff == 0:
		diff = max((freq[x] for x in start))
	j = None
	for (i, x) in enumerate(start):
		freq[x] -= diff
		if j is None and freq[x] >= 0:
			j = i
	return (min(m, end - start[j] + 1), [x for x in start if freq[x] > 0])
for _ in range(int(input())):
	tmp = list(map(int, input().split()))
	(n, skills) = (tmp[0], tmp[1:])
	if not n:
		print(0)
		continue
	freq = Counter(skills)
	prev = None
	start = []
	m = n
	for skill in sorted(freq.keys()):
		if prev is None:
			start.append(skill)
		elif skill - prev == 1:
			if freq[skill] > freq[prev]:
				start.append(skill)
			elif freq[skill] < freq[prev]:
				(m, start) = find_min(m, start, prev, freq[prev] - freq[skill], freq)
		elif skill - prev > 1:
			(m, tmp) = find_min(m, start, prev, 0, freq)
			start = []
			start.append(skill)
		prev = skill
	(m, tmp) = find_min(m, start, prev, 0, freq)
	print(m)


import collections
for _ in range(int(input())):
	l = input().split()
	applicants = collections.Counter(map(int, l[1:]))
	teams = collections.deque()
	total = 0
	last = -10000000
	m = int(l[0])
	if m == 0:
		print(0)
		continue
	for a in sorted(applicants):
		if a - 1 != last:
			for (c, n) in teams:
				if c:
					m = min(m, last - n + 1)
			teams = collections.deque()
			a_count = applicants[a]
			teams.append([a_count, a])
			total = a_count
		elif applicants[a] > total:
			a_count = applicants[a] - total
			teams.append([a_count, a])
			total = applicants[a]
		else:
			ending = total - applicants[a]
			while ending:
				(c, n) = teams[0]
				if c:
					m = min(m, last - n + 1)
				if ending >= c:
					ending -= c
					teams.popleft()
				else:
					teams[0][0] -= ending
					ending = 0
			total = applicants[a]
		last = a
	for (c, n) in teams:
		if c:
			m = min(m, last - n + 1)
	print(m)


from collections import Counter

def smallest_set(start, end, c):
	d = {}
	d[start - 1] = []
	for i in range(start, end + 1):
		d[i] = []
		prev_len = len(d[i - 1])
		new_lists = c[i] - prev_len
		if new_lists > 0:
			d[i] = [1] * new_lists
		if prev_len > 0:
			num_appends = min(prev_len, new_lists + prev_len)
			d[i - 1].sort()
			d[i] += [x + 1 for x in d[i - 1][:num_appends]]
			d[i - 1] = d[i - 1][num_appends:]
	ans = d[end][0]
	for i in range(start, end + 1):
		if len(d[i]) > 0:
			ans = min(ans, min(d[i]))
			if ans == 1:
				return 1
	return ans

def find_lowest_range(l, n):
	c = Counter(l)
	i = 0
	mini = n
	while i < len(l):
		end = i
		while end < n and (l[i] == l[end] or l[end] - l[end - 1] <= 1):
			end += 1
		end -= 1
		if end == i:
			return 1
		mini = min(mini, smallest_set(l[i], l[end], c))
		if mini == 1:
			return 1
		i = end + 1
	return mini
t = int(input())
for _ in range(t):
	l = list(map(int, input().split()))
	if l[0] == 0:
		print(0)
		continue
	n = l[0]
	l = sorted(l[1:])
	print(find_lowest_range(l, n))


from collections import Counter

def smallest_set(start, end, c):
	d = {}
	d[start - 1] = []
	for i in range(start, end + 1):
		d[i] = []
		prev_len = len(d[i - 1])
		new_lists = c[i] - prev_len
		if new_lists > 0:
			d[i] = [1] * new_lists
		if prev_len > 0:
			num_appends = min(prev_len, new_lists + prev_len)
			d[i - 1].sort()
			d[i] += [x + 1 for x in d[i - 1][:num_appends]]
			d[i - 1] = d[i - 1][num_appends:]
	ans = d[end][0]
	for i in range(start, end + 1):
		if len(d[i]) > 0:
			ans = min(ans, min(d[i]))
			if ans == 1:
				return 1
	return ans

def find_lowest_range(l, n):
	c = Counter(l)
	i = 0
	mini = n
	while i < len(l):
		end = i
		while end < n and (l[i] == l[end] or l[end] - l[end - 1] <= 1):
			end += 1
		end -= 1
		if end == i:
			return 1
		mini = min(mini, smallest_set(l[i], l[end], c))
		if mini == 1:
			return 1
		i = end + 1
	return mini
t = int(input())
for _ in range(t):
	l = list(map(int, input().split()))
	if l[0] == 0:
		print(0)
		continue
	n = l[0]
	l = sorted(l[1:])
	print(find_lowest_range(l, n))


import sys
from collections import Counter
from typing import List

def inner(conts, start, end):
	teams = {start - 1: []}
	for cont in range(start, end + 1):
		teams[cont] = []
		new_conts = conts[cont]
		prev_cont_team_count = len(teams[cont - 1])
		new_teams = new_conts - prev_cont_team_count
		if new_teams:
			teams[cont] += [1] * new_teams
		if prev_cont_team_count:
			prev_teams = min(prev_cont_team_count, new_conts)
			teams[cont - 1].sort()
			teams[cont] += [x + 1 for x in teams[cont - 1][:prev_teams]]
			teams[cont - 1] = teams[cont - 1][prev_teams:]
	smallest = teams[end][0]
	for cont in range(start, end + 1):
		if len(teams[cont]) > 0:
			smallest = min(smallest, min(teams[cont]))
			if smallest == 1:
				return 1
	return smallest

def get_smallest_team_count(conts: List[int]) -> int:
	if not conts:
		return 0
	conts.sort()
	start = 0
	conts_ = Counter(conts)
	conts_len = len(conts)
	smallest = conts_len
	while start < conts_len:
		end = start
		while end < conts_len and (conts[start] == conts[end] or conts[end] - conts[end - 1] <= 1):
			end += 1
		end -= 1
		if end == start:
			return 1
		smallest = min(smallest, inner(conts_, conts[start], conts[end]))
		if smallest == 1:
			return 1
		start = end + 1
	return smallest

def main():
	input_lines = sys.stdin.readlines()
	input_lines.pop(0)
	for (i, input_line) in enumerate(input_lines):
		conts = list(map(int, input_line.strip().split(' ')))
		conts.pop(0)
		print(get_smallest_team_count(conts))
main()


from collections import Counter

def smallest_set(start, end, c):
	d = {}
	d[start - 1] = []
	for i in range(start, end + 1):
		d[i] = []
		prev_len = len(d[i - 1])
		new_lists = c[i] - prev_len
		if new_lists > 0:
			d[i] = [1] * new_lists
		if prev_len > 0:
			num_appends = min(prev_len, new_lists + prev_len)
			d[i - 1].sort()
			d[i] += [x + 1 for x in d[i - 1][:num_appends]]
			d[i - 1] = d[i - 1][num_appends:]
	ans = d[end][0]
	for i in range(start, end + 1):
		if len(d[i]) > 0:
			ans = min(ans, min(d[i]))
			if ans == 1:
				return 1
	return ans

def find_lowest_range(l, n):
	c = Counter(l)
	i = 0
	mini = n
	while i < len(l):
		end = i
		while end < n and (l[i] == l[end] or l[end] - l[end - 1] <= 1):
			end += 1
		end -= 1
		if end == i:
			return 1
		mini = min(mini, smallest_set(l[i], l[end], c))
		if mini == 1:
			return 1
		i = end + 1
	return mini
t = int(input())
for _ in range(t):
	l = list(map(int, input().split()))
	if l[0] == 0:
		print(0)
		continue
	n = l[0]
	l = sorted(l[1:])
	print(find_lowest_range(l, n))


import itertools, operator, collections, heapq
t = int(input())
for _ in range(t):
	nums = sorted(map(int, input().split()[1:]))
	if len(nums) == 0:
		print(0)
		continue
	ending = collections.defaultdict(list)
	for n in nums:
		if n - 1 in ending:
			smallest = min(ending[n - 1], key=len)
			ending[n - 1].remove(smallest)
			if not ending[n - 1]:
				del ending[n - 1]
			smallest.append(n)
			ending[n].append(smallest)
		else:
			ending[n].append([n])
	print(min((min(map(len, x)) for x in ending.values())))


from heapq import heappush, heappop
from collections import defaultdict

def teamForm(lst):
	if len(lst) == 0:
		return 0
	lst = sorted(lst)
	hm = defaultdict(list)
	for elem in lst:
		current = 0
		if elem - 1 in hm:
			if len(hm[elem - 1]) != 0:
				current = heappop(hm[elem - 1])
		current += 1
		heappush(hm[elem], current)
	mini = float('inf')
	for key in hm:
		if len(hm[key]) != 0:
			mini = min(mini, heappop(hm[key]))
	return mini
string = input()
for test_case in range(int(string)):
	string = input()
	lst = list(map(lambda x: int(x), string.split()))
	print(teamForm(lst[1:]))


from collections import Counter

def smallest_set(start, end, c):
	d = {}
	d[start - 1] = []
	for i in range(start, end + 1):
		d[i] = []
		prev_len = len(d[i - 1])
		new_lists = c[i] - prev_len
		if new_lists > 0:
			d[i] = [1] * new_lists
		if prev_len > 0:
			num_appends = min(prev_len, new_lists + prev_len)
			d[i - 1].sort()
			d[i] += [x + 1 for x in d[i - 1][:num_appends]]
			d[i - 1] = d[i - 1][num_appends:]
	ans = d[end][0]
	for i in range(start, end + 1):
		if len(d[i]) > 0:
			ans = min(ans, min(d[i]))
			if ans == 1:
				return 1
	return ans

def find_lowest_range(l, n):
	c = Counter(l)
	i = 0
	mini = n
	while i < len(l):
		end = i
		while end < n and (l[i] == l[end] or l[end] - l[end - 1] <= 1):
			end += 1
		end -= 1
		if end == i:
			return 1
		mini = min(mini, smallest_set(l[i], l[end], c))
		if mini == 1:
			return 1
		i = end + 1
	return mini
t = int(input())
for _ in range(t):
	l = list(map(int, input().split()))
	if l[0] == 0:
		print(0)
		continue
	n = l[0]
	l = sorted(l[1:])
	print(find_lowest_range(l, n))


from collections import Counter

def smallest_set(start, end, c):
	d = {}
	d[start - 1] = []
	for i in range(start, end + 1):
		d[i] = []
		prev_len = len(d[i - 1])
		new_lists = c[i] - prev_len
		if new_lists > 0:
			d[i] = [1] * new_lists
		if prev_len > 0:
			num_appends = min(prev_len, new_lists + prev_len)
			d[i - 1].sort()
			d[i] += [x + 1 for x in d[i - 1][:num_appends]]
			d[i - 1] = d[i - 1][num_appends:]
	ans = d[end][0]
	for i in range(start, end + 1):
		if len(d[i]) > 0:
			ans = min(ans, min(d[i]))
			if ans == 1:
				return 1
	return ans

def find_lowest_range(l, n):
	c = Counter(l)
	i = 0
	mini = n
	while i < len(l):
		end = i
		while end < n and (l[i] == l[end] or l[end] - l[end - 1] <= 1):
			end += 1
		end -= 1
		if end == i:
			return 1
		mini = min(mini, smallest_set(l[i], l[end], c))
		if mini == 1:
			return 1
		i = end + 1
	return mini
t = int(input())
for _ in range(t):
	l = list(map(int, input().split()))
	if l[0] == 0:
		print(0)
		continue
	n = l[0]
	l = sorted(l[1:])
	print(find_lowest_range(l, n))


from collections import Counter

def smallest_set(start, end, c):
	d = {}
	d[start - 1] = []
	for i in range(start, end + 1):
		d[i] = []
		prev_len = len(d[i - 1])
		new_lists = c[i] - prev_len
		if new_lists > 0:
			d[i] = [1] * new_lists
		if prev_len > 0:
			num_appends = min(prev_len, new_lists + prev_len)
			d[i - 1].sort()
			d[i] += [x + 1 for x in d[i - 1][:num_appends]]
			d[i - 1] = d[i - 1][num_appends:]
	ans = d[end][0]
	for i in range(start, end + 1):
		if len(d[i]) > 0:
			ans = min(ans, min(d[i]))
			if ans == 1:
				return 1
	return ans

def find_lowest_range(l, n):
	c = Counter(l)
	i = 0
	mini = n
	while i < len(l):
		end = i
		while end < n and (l[i] == l[end] or l[end] - l[end - 1] <= 1):
			end += 1
		end -= 1
		if end == i:
			return 1
		mini = min(mini, smallest_set(l[i], l[end], c))
		if mini == 1:
			return 1
		i = end + 1
	return mini
t = int(input())
for _ in range(t):
	l = list(map(int, input().split()))
	if l[0] == 0:
		print(0)
		continue
	n = l[0]
	l = sorted(l[1:])
	print(find_lowest_range(l, n))


from collections import Counter

def smallest_set(start, end, c):
	d = {}
	d[start - 1] = []
	for i in range(start, end + 1):
		d[i] = []
		prev_len = len(d[i - 1])
		new_lists = c[i] - prev_len
		if new_lists > 0:
			d[i] = [1] * new_lists
		if prev_len > 0:
			num_appends = min(prev_len, new_lists + prev_len)
			d[i - 1].sort()
			d[i] += [x + 1 for x in d[i - 1][:num_appends]]
			d[i - 1] = d[i - 1][num_appends:]
	ans = d[end][0]
	for i in range(start, end + 1):
		if len(d[i]) > 0:
			ans = min(ans, min(d[i]))
			if ans == 1:
				return 1
	return ans

def find_lowest_range(l, n):
	c = Counter(l)
	i = 0
	mini = n
	while i < len(l):
		end = i
		while end < n and (l[i] == l[end] or l[end] - l[end - 1] <= 1):
			end += 1
		end -= 1
		if end == i:
			return 1
		mini = min(mini, smallest_set(l[i], l[end], c))
		if mini == 1:
			return 1
		i = end + 1
	return mini
t = int(input())
for _ in range(t):
	l = list(map(int, input().split()))
	if l[0] == 0:
		print(0)
		continue
	n = l[0]
	l = sorted(l[1:])
	print(find_lowest_range(l, n))


import heapq
from collections import defaultdict

def maxMinTeamSize(skills):
	skills.sort()
	teams = defaultdict(list)
	for skill in skills:
		if skill - 1 not in teams:
			teamToInsert = 1
		elif len(teams[skill - 1]) == 0:
			teamToInsert = 1
		else:
			smallestTeam = heapq.heappop(teams[skill - 1])
			teamToInsert = smallestTeam + 1
		heapq.heappush(teams[skill], teamToInsert)
	minimumTeamSize = len(skills)
	for (_skillLevel, teamsEndingInSkillLevel) in teams.items():
		for teamSize in teamsEndingInSkillLevel:
			minimumTeamSize = min(minimumTeamSize, teamSize)
	return minimumTeamSize
t = int(input())
for i in range(t):
	inp = [int(ch) for ch in input().split()]
	print(maxMinTeamSize(inp[1:]))


import sys
sys.stdin.readline()

def team_formation(line):
	counts = {}
	for i in [int(x) for x in line.split()[1:]]:
		counts[i] = counts.get(i, 0) + 1
	lst = sorted(counts.items())
	c = [lst[0][1]]
	for i in range(1, len(lst)):
		if lst[i][0] - lst[i - 1][0] > 1:
			c.append(0)
		c.append(lst[i][1])
	min_count = len(lst)
	q = [0] * c[0]
	for i in range(1, len(c)):
		if c[i - 1] <= c[i]:
			q += [i] * (c[i] - c[i - 1])
		else:
			min_count = min(min_count, i - q[-c[i] - 1])
	if q:
		return min(min_count, len(c) - q[-1])
	return min_count
for line in sys.stdin.readlines():
	if line.strip() is '0':
		print(0)
	else:
		print(team_formation(line))