​A 1-indexed array is called *positive* if every element of the array is greater than or equal to the index on which it lies. Formally, an array B of size M is called positive if B_{i} ≥ i for each 1≤ i ≤ M.

For example, the arrays [1], [2, 2], [3, 2, 4, 4] are positive while the arrays [2, 1], [3, 1, 2] are not positive.

You are given an array A containing N integers. You want to distribute all elements of the array into some positive arrays. The elements of a positive array might not occur in the order they appear in the array A.

Find the minimum number of positive arrays that the elements of the array A can be divided into.

Please see the sample cases below for more clarity.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of two lines of input.
- The first line of each test case contains an integer N — the number of elements in the array A.
- The next line contains N space-separated integers A_{1}, A_{2},\ldots, A_{N} — the elements of array A.

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

For each test case, output on a new line the minimum number of positive arrays that the elements of the array A can be divided into.
​

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

$1 ≤ T ≤ 10^{4}$
$1 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ N$
- The sum of $N$ over all test cases won't exceed $2\cdot 10^{5}$.

----- Sample Input 1 ------ 
5
3
2 3 3
4
3 1 1 2
3
1 1 1
5
1 2 2 4 5
6
3 2 1 2 2 1

----- Sample Output 1 ------ 
1
2
3
2
3

----- explanation 1 ------ 
Test case $1$: The given array is already positive. So the optimal division is $[2,3,3]$.

Test case $2$: One possible division is $[1, 2], [1, 3]$.

Test case $3$: The only possible division is $[1],[1],[1]$.

Test case $4$: One possible division is $[1, 2, 5], [2, 4]$.

Test case $5$: One possible division is $[1, 2, 3], [1], [2,2]$.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Data structures

Greedy algorithms


Solutions:
from math import ceil
for _ in range(int(input())):
	n = int(input())
	all = [int(i) for i in input().split()]
	ans = 0
	all.sort()
	for i in range(n):
		ans = max(ans, ceil((i + 1) / all[i]))
	print(ans)


from collections import defaultdict
import math
for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	d = defaultdict(int)
	for i in a:
		d[i] += 1
	s = 1
	el = 0
	for i in range(1, max(a) + 1):
		if d[i] > s * i - el:
			s += math.ceil((d[i] - s * i + el) / i)
		el += d[i]
	print(s)


t = int(input())
for i in range(t):
	n = int(input())
	A = [int(x) for x in input().split()]
	A.sort()
	count = 1
	B = []
	for i in range(n - 1):
		if A[i] != A[i + 1]:
			if (i + 1) % A[i] == 0:
				B.append((i + 1) // A[i])
			else:
				B.append((i + 1) // A[i] + 1)
	if n % A[n - 1] == 0:
		B.append(n // A[n - 1])
	else:
		B.append(n // A[n - 1] + 1)
	print(max(B))


for i in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	A.sort()
	print(max([j // A[j] + 1 for j in range(N)]))


import math
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	count = {}
	for c in arr:
		count[c] = 1 + count.get(c, 0)
	ans = 0
	k = 0
	for i in range(1, n + 1):
		val = count.get(i, 0)
		ans = max(ans, math.ceil((val + k) / i))
		k += val
	print(ans)


import math
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	ans = 0
	for i in range(n):
		ans = max(ans, math.ceil((i + 1) / a[i]))
	print(int(ans))


from math import ceil
T = int(input())
final = list()
for t in range(T):
	N = int(input())
	array = sorted(map(int, input().split()))
	(ans, index) = (0, 1)
	for number in array:
		ans = max(ceil(index / number), ans)
		index += 1
	final.append(ans)
for f in final:
	print(f)


from heapq import heapify, heappush, heappop
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	heapify(arr)
	list1 = [1]
	heapify(list1)
	while arr:
		x = heappop(arr)
		y = heappop(list1)
		if x >= y:
			y += 1
			heappush(list1, y)
		else:
			heappush(list1, y)
			heappush(list1, 2)
	print(len(list1))


import bisect
for z in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	a.sort()
	c = 0
	while n > 0:
		i = 1
		while bisect.bisect_left(a, i) != n:
			a.pop(bisect.bisect_left(a, i))
			i += 1
			n -= 1
		c += 1
	print(c)


for i in range(int(input())):
	lens = int(input())
	array = list(map(int, input().split()))
	array.sort()
	k = 0
	for i in range(len(array)):
		a = i + 1
		b = array[i]
		k = max(-(-a // b), k)
	print(k)


class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))
t = int(input())
for j in range(t):
	length = int(input())
	arr = SortedList(list(map(int, input().split())))
	c = 0
	while len(arr) > 0:
		i = 1
		while arr.bisect_left(i) != len(arr):
			arr.pop(arr.bisect_left(i))
			i += 1
		c += 1
	print(c)


import bisect
import heapq
t = int(input())
for _ in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	A.sort()
	q = []
	res = 0
	for x in A:
		if not q or (q and q[0] > x):
			heapq.heappush(q, 2)
			res += 1
		else:
			heapq.heappush(q, heapq.heappop(q) + 1)
	print(res)


import heapq
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr = sorted(arr)
	q = list()
	heapq.heappush(q, 1)
	for i in range(n):
		if arr[i] >= q[0]:
			heapq.heappush(q, q[0] + 1)
			heapq.heappop(q)
		else:
			heapq.heappush(q, 2)
	print(len(q))


import collections as clts
import math
import heapq

def gcd(x, y):
	if y == 0:
		return x
	else:
		return gcd(y, x % y)

def lcm(x, y):
	return int(x / gcd(x, y) * y)
for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	valid = True
	for i in range(N):
		if A[i] < i + 1:
			valid = False
			break
	if valid:
		print(1)
	else:
		A = sorted(A)
		ele = []
		for i in range(N):
			if len(ele) == 0:
				heapq.heappush(ele, 1)
			else:
				e = heapq.heappop(ele)
				if A[i] >= e + 1:
					heapq.heappush(ele, e + 1)
				else:
					heapq.heappush(ele, 1)
					heapq.heappush(ele, e)
		print(len(ele))


import sys
from os import path
if path.exists('Input.txt'):
	sys.stdin = open('Input.txt', 'r')
	sys.stdout = open('Output.txt', 'w')
import math
from collections import deque

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	d = dict()
	for ii in range(1, n + 1):
		d[ii] = 0
	for i in range(n):
		d[a[i]] += 1
	ans = 0
	y = 0
	for i in range(1, n + 1):
		y += d[i]
		x = math.ceil(y / i)
		ans = max(ans, x)
	print(ans)
for _ in range(int(input())):
	solve()


from queue import PriorityQueue
case = int(input())
for _ in range(case):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	arr.sort()
	que = PriorityQueue()
	que.put(1)
	for i in range(n):
		val = que.get()
		if arr[i] >= val:
			que.put(val + 1)
		else:
			que.put(val)
			que.put(2)
	print(que.qsize())


import sys, math, bisect, heapq, collections, itertools, functools
inum = lambda : int(sys.stdin.readline())
imap = lambda : map(int, sys.stdin.readline().split())
itup = lambda : tuple(map(int, sys.stdin.readline().split()))
isor = lambda : sorted(map(int, sys.stdin.readline().split()))
isor2 = lambda nums: sorted(nums, key=lambda num1: (num1[0], num1[1]))
ilis = lambda : [int(zz) for zz in sys.stdin.readline().split()]
dd = lambda : collections.defaultdict(lambda : 0)
adjlist = lambda : collections.defaultdict(lambda : [])
lcm = lambda num1, num2: num1 * num2 // math.gcd(num1, num2)
npr = lambda num1, num2: math.factorial(num1) // math.factorial(num1 - num2)
lowerpower = lambda num1, num2: pow(num2, math.floor(math.log(num1, num2)))
upperpower = lambda num1, num2: pow(num2, math.ceil(math.log(num1, num2)))
isperfectsquare = lambda num1: math.ceil(math.log(num1, 2)) == math.floor(math.log(num1, 2))
ncr = lambda num1, num2: math.factorial(num1) // (math.factorial(num2) * math.factorial(num1 - num2))
filtereven = lambda nums: list(filter(lambda num1: num1 % 2 == 0, nums))
filteroddd = lambda nums: list(filter(lambda num1: num1 % 2 != 0, nums))
fact = lambda num1: functools.reduce(lambda num2, num3: num2 * num3, range(1, num1 + 1))
freqarray = lambda nums: collections.Counter(nums)
bitsetarray = lambda nums: [int(num1) for num1 in bin(nums)[2:]]
lengthbitset = lambda num1: math.ceil(math.log(num1 + 0.1, 2))
bit_check = lambda num1, num2: num1 & 1 << num2
bit_set = lambda num1, num2: num1 | 1 << num2
bit_unset = lambda num1, num2: num1 & ~(1 << num2)
bit_toggle = lambda num1, num2: num1 ^ 1 << num2
minheap = lambda nums: 1 if heapq.heapify(nums) == None else 0
maxheap = lambda nums: 1 if heapq._heapify_max(nums) == None else 0
lowerbound = lambda nums, key, start, stop: bisect.bisect_left(nums, key, lo=start, hi=stop)
upperbound = lambda nums, key, start, stop: bisect.bisect_right(nums, key, lo=start, hi=stop)
inorder = lambda root: inorder(root.left) + [root.val] + inorder(root.right) if root else []
prefixsumarray = lambda nums: list(itertools.accumulate(nums, lambda num1, num2: num1 + num2))
suffixsumarray = lambda nums: prefixsum(reversed(nums))
grid = lambda rows, cols: [[0 for j in range(cols)] for idx in range(rows)]
palindromeindices = lambda num1: [(num1 // 2 - i - (0 if num1 & 1 else 1), num1 // 2 + i) for i in range(num1 // 2 + (1 if num1 & 1 else 0))]
onum = lambda num1: '%d' % num1
omap = lambda num1, num2: '%d %d' % (num1, num2)
olis = lambda nums: ' '.join((str(nums[idx]) for idx in range(len(nums))))
odict = lambda nums: '\n'.join((str('%idx: %s' % (num1[0], ' '.join((str(num2) for num2 in num1[1])))) for num1 in zip(nums.keys(), nums.values())))
ogrid = lambda grid: '\n'.join((' '.join((str(num1) for num1 in nums)) for nums in grid))
tcs = 1 if not True else int(input())
for tc in range(1, tcs + 1):
	n = inum()
	arr = isor()
	cur = ans = 1
	while len(arr) > 0:
		pos = bisect.bisect_left(arr, cur)
		if pos != len(arr):
			arr.pop(pos)
			cur += 1
		else:
			cur = 1
			ans += 1
	print(ans)


from heapq import heapify, heappush, heappop
t = int(input())
while t > 0:
	n = int(input())
	array = list(map(int, input().split(' ')[:n]))
	array.sort()
	minheap = [0]
	heapify(minheap)
	for num in array:
		temp = heappop(minheap)
		if temp < num:
			temp += 1
			heappush(minheap, temp)
		else:
			heappush(minheap, temp)
			heappush(minheap, 1)
	print(len(minheap))
	t -= 1


test = int(input())
while test:
	test -= 1
	val = int(input())
	A = input()
	A = list(map(int, A.split(' ')))
	maxIndex = max(max(A) + 1, val + 1)
	newA = [0] * maxIndex
	for i in A:
		newA[i] += 1
	sumx = 0
	k = 0
	for i in range(1, val + 1):
		sumx += newA[i]
		k = max(k, (sumx + i - 1) // i)
	print(k)


from queue import PriorityQueue
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	a = [int(x) for x in input().split()]
	q = PriorityQueue()
	q.put(1)
	a.sort()
	for i in a:
		minIndex = q.get()
		if i >= minIndex:
			q.put(minIndex + 1)
		else:
			q.put(2)
			q.put(minIndex)
	print(q.qsize())


t = int(input())
c = 0
for i in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	a.sort()
	print(max([i // a[i] + 1 for i in range(n)]))


import math
for i in range(int(input())):
	n = int(input())
	nlist = list(map(int, input().split()))
	nlist.sort()
	ans = 0
	count = 1
	filled = 0
	for j in range(1, n):
		if nlist[j] != nlist[j - 1]:
			curr = nlist[j - 1] * ans - filled
			filled += count
			if count >= curr:
				count -= curr
				ans += math.ceil(count / nlist[j - 1])
			count = 1
		else:
			count += 1
	curr = nlist[n - 1] * ans - filled
	filled += count
	if count >= curr:
		count -= curr
		ans += math.ceil(count / nlist[n - 1])
	print(ans)


import heapq

def solve(n, arr):
	arr = sorted(arr)
	q = list()
	heapq.heappush(q, 1)
	for i in range(n):
		if arr[i] >= q[0]:
			heapq.heappush(q, q[0] + 1)
			heapq.heappop(q)
		else:
			heapq.heappush(q, 2)
	return len(q)
t = int(input())
while t > 0:
	n = int(input())
	arr = [int(x) for x in input().split()]
	print(solve(n, arr))
	t -= 1


import collections
t = int(input())
for _ in range(0, t):
	N = int(input())
	A = list(map(int, input().split()))
	A.sort()
	B = collections.Counter(A)
	(L, R) = (0, N + 1)
	while L + 1 < R:
		M = (L + R) // 2
		ans = 1
		C = []
		for i in range(M):
			C.append([])
		j = 0
		i = 0
		while i < N:
			if len(C[j]) < A[i]:
				C[j].append(A[i])
				i += 1
				ans = 0
			else:
				j += 1
			if j >= M:
				j %= M
				if ans:
					break
				ans = 1
		if i == N:
			R = M
		else:
			L = M
	print(R)


import copy
import math

def solve(a, b):
	a.sort()
	b = [[a[0], 1]]
	c = 0
	for i in range(1, len(a)):
		if a[i] == b[c][0]:
			b[c][1] += 1
		else:
			c += 1
			b.append([a[i], 1])
	c = 0
	d = 0
	while len(b) != 0:
		r = 0
		c = 0
		e = len(b)
		for i in range(e):
			if b[i - c][0] - r >= b[i - c][1]:
				r += b[i - c][1]
				b.pop(i - c)
				c += 1
			else:
				b[i - c][1] -= b[i - c][0] - r
				r = b[i - c][0]
		d += 1
	print(d)
for i in range(int(input())):
	a = int(input())
	b = list(map(int, input().strip().split()))
	solve(b, a)


for _ in range(int(input())):
	sizeOfInput = int(input())
	tempList = list(map(int, input().split()))
	dict = {}
	for x in tempList:
		dict[x] = dict.get(x, 0) + 1
	sortedDict = {}
	for key in sorted(dict.keys()):
		sortedDict[key] = dict[key]
	AnswerList = []
	numberOfAnswerLists = 0
	for element in list(sortedDict.keys()):
		nextList = 0
		for i in range(1, sortedDict[element] + 1):
			if numberOfAnswerLists == 0:
				AnswerList.append([element])
				numberOfAnswerLists += 1
			else:
				inserted = False
				for lists in range(nextList, numberOfAnswerLists):
					if element >= len(AnswerList[lists]) + 1:
						AnswerList[lists].append(element)
						nextList = lists
						inserted = True
						break
				if inserted == False:
					AnswerList.append([element])
					nextList = numberOfAnswerLists
					numberOfAnswerLists += 1
	print(numberOfAnswerLists)


import bisect
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	slst = [1]
	for i in l:
		if i >= slst[0]:
			tmp = slst[0]
			del slst[0]
			bisect.insort(slst, tmp + 1)
		else:
			slst = [2] + slst
	print(len(slst))


import heapq
for t in range(int(input())):
	n = int(input())
	lst = [int(x) for x in input().split()]
	lst.sort()
	lst1 = []
	heapq.heapify(lst1)
	heapq.heappush(lst1, 1)
	cntr = 1
	for x in lst[1:]:
		if x > lst1[0]:
			a = heapq.heappop(lst1)
			heapq.heappush(lst1, a + 1)
			pass
		else:
			cntr += 1
			heapq.heappush(lst1, 1)
	print(cntr)


from queue import PriorityQueue
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	q = PriorityQueue()
	q.put(1)
	for item in arr:
		ln = q.get()
		if item >= ln:
			ln += 1
		else:
			q.put(2)
		q.put(ln)
	print(q.qsize())


import heapq
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	heap = []
	heapq.heappush(heap, 1)
	for i in range(n):
		cur = l[i]
		top = heapq.heappop(heap)
		if cur >= top:
			top += 1
		else:
			heapq.heappush(heap, 2)
		heapq.heappush(heap, top)
	print(len(heap))


import math
for _ in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	arr.sort()
	ans = 0
	for i in range(len(arr)):
		k = math.ceil((i + 1) / arr[i])
		ans = max(ans, k)
	print(ans)


from math import ceil
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))[:n]
	c = 0
	l.sort()
	for i in range(n):
		c = max(c, ceil((i + 1) / l[i]))
	print(c)


from queue import PriorityQueue
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	q = PriorityQueue()
	q.put((0, 1))
	for item in arr:
		(ln, mn) = q.get()
		if item >= ln + 1 and item >= mn:
			ln += 1
			mn = min(mn, item)
		else:
			q.put((1, item))
		q.put((ln, mn))
	print(q.qsize())


import heapq
from math import gcd, sqrt, ceil

def ti():
	return tuple(map(int, input().split()))

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

def si():
	return input().split()

def ii():
	return int(input())

def ip():
	return input()
for tastcas in range(int(input())):
	n = ii()
	a = li()
	a.sort()
	ans = 0
	for i in range(n):
		ans = max(ans, ceil((i + 1) / a[i]))
	print(ans)