A certain parallel universe has exactly N people living in it.

The i-th of these N people claims that they are the parent of exactly A_{i} of these N people.

However, some of these people might be lying — the i-th person may be either telling the truth (in which case they have exactly A_{i} children) or lying (in which case they can have any number of children).

It is known that each person has at most one parent. Further, as one would expect, it is not allowed for a person's child to also be their ancestor.

What is the maximum possible number of truth-tellers in this universe?

------ 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 a single integer N, the number of people.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \ldots, A_{N}. 

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

For each test case, output on a new line the maximum number of people that can be telling the truth.

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

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

------ subtasks ------ 

Subtask 1 (20 points):
$1 ≤ T ≤ 5$
$1 ≤ N ≤ 20$
Subtask 2 (80 points):
No further constraints.

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

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

----- explanation 1 ------ 
Test case $1$: Both people can be telling the truth, with the first person being the parent of the second.

Test case $2$: If both people were telling the truth, they would be each others' parents — and that is not allowed. Hence, at most one of them can be telling the truth.

Test case $3$: The first and third people cannot be telling the truth at the same time. However, it is possible for the first and second people to be truthful — person $1$ can be the parent of person $2$ and person $3$. Hence, the answer is $2$.

Test case $4$: There are several ways to pick $2$ people to be telling the truth — for example,
- The parent of person $2$ and person $3$ is person $1$
- The parent of person $1$ and person $5$ is person $4$

in which case persons number $1$ and $4$ would be telling the truth.

However, it can be shown that it is impossible for any three of them to be simultaneously telling the truth.

Source: codechef | Difficulty: MEDIUM
Tags: Graph algorithms

Sorting

Greedy algorithms

Tree algorithms

Data structures


Solutions:
t = int(input())
while t > 0:
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	tot = 0
	c = 0
	for i in arr:
		tot += i
		if tot < n:
			c += 1
		else:
			break
	print(c)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	res = 0
	c = 0
	for i in a:
		res += i
		if res < n:
			c += 1
		else:
			break
	print(c)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	pre = [a[0]]
	for i in range(1, n):
		pre.append(pre[-1] + a[i])
	(l, r) = (0, n - 1)
	ans = 0
	while l <= r:
		m = (l + r) // 2
		if pre[m] <= n - 1:
			ans = m + 1
			l = m + 1
		else:
			r = m - 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	l = 0
	count = 0
	for i in a:
		l += i
		if l < n:
			count += 1
		else:
			break
	print(count)


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	a.sort()
	c = 0
	v = n - 1
	for x in a:
		if x <= v:
			c = c + 1
			v = v - x
	print(c)


t = int(input())
for i in range(t):
	num = int(input())
	a = [int(x) for x in input().split()]
	a.sort()
	val = num - 1
	t = 0
	for i in range(num):
		if a[i] <= val:
			t += 1
			val = val - a[i]
	print(t)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	(count, total) = (0, n - 1)
	for i in range(n):
		if arr[i] <= total:
			count += 1
			total -= arr[i]
	print(count)


t = int(input())
for i in range(t):
	n = list(map(int, input().split()))
	p = [int(ele) for ele in input().strip().split()]
	p.sort()
	s = 0
	c = 0
	for i in range(n[0]):
		s += p[i]
		if s < n[0]:
			c += 1
		else:
			break
	print(c)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	children = 0
	answer = 0
	a.sort()
	for i in a:
		children = i + children
		if children > n - 1:
			break
		answer = answer + 1
	print(answer)


for _ in range(int(input())):
	truth = 0
	N = int(input())
	A = list(map(int, input().split()))
	A.sort()
	ttl = 0
	for per in A:
		ttl += per
		if ttl < N:
			truth += 1
		else:
			break
	print(truth)


T = int(input())
for _ in range(T):
	n = int(input())
	a = [int(x) for x in input().split()]
	a.sort()
	total = 0
	for ai in a:
		if ai < n:
			total += 1
			n -= ai
	print(total)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	i = 0
	sum = a[0]
	k = n
	while sum <= k - 1:
		k = k - a[i]
		i += 1
		if i == n:
			break
		sum = a[i]
	print(i)


import heapq
testCases = int(input())
for i in range(testCases):
	N = int(input())
	arr = []
	for j in input().split(' '):
		heapq.heappush(arr, int(j))
	lenn = len(arr)
	maxTruths = 0
	counter = 0
	while counter + 1 < N and len(arr) > 0:
		popedElement = heapq.heappop(arr)
		counter += popedElement
		maxTruths += 1
	if counter == 0:
		print(lenn)
	elif counter >= N:
		print(maxTruths - 1)
	else:
		print(maxTruths)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	t = 0
	ans = 0
	for x in a:
		t += x
		if t > n - 1:
			break
		else:
			ans += 1
	print(ans)


T = int(input())
for t in range(T):
	n = int(input())
	s = input().split()
	arr = [int(x) for x in s]
	arr.sort()
	count = 0
	total = 0
	for el in arr:
		total += el
		if total < n:
			count += 1
		else:
			break
	print(count)


t = int(input())
for _ in range(t):
	n = int(input())
	array = list(map(int, input().split()))
	array.sort()
	c1 = 0
	c2 = 0
	for k in range(2):
		o = 0
	for i in array:
		c1 += i
		if c1 < n:
			c2 += 1
		else:
			break
	print(c2)


for _ in range(int(input())):
	n = int(input())
	ar = list(map(int, input().split()))
	tru = 0
	ar.sort()
	for i in range(n):
		if ar[i] <= n - 1:
			tru = tru + 1
			n = n - ar[i]
	print(tru)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	c = 0
	m = 0
	for i in l:
		c += i
		m += 1
		if c > n - 1:
			m -= 1
	print(m)


tc = int(input())
while tc:
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	c1 = 0
	c2 = 0
	for i in arr:
		c1 += i
		if c1 < n:
			c2 += 1
		else:
			break
	print(c2)
	tc -= 1


t = int(input())
while t:
	t = t - 1
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	c = 0
	a = 0
	for i in range(n):
		if c + l[i] < n:
			c = c + l[i]
			a = a + 1
		else:
			break
	print(a)


T = int(input())
for tc in range(T):
	N = int(input())
	lst = list(map(int, input().split()))
	lst.sort()
	checker = 0
	truth = 0
	for i in range(N):
		checker += lst[i]
		if checker >= N:
			break
		truth += 1
	print(truth)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	ans = 0
	included = 0
	i = 0
	while i < n and included + a[i] < n:
		included += a[i]
		ans += 1
		i += 1
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	tot = 0
	ans = 0
	for i in a:
		tot += i
		if tot >= n:
			break
		ans += 1
	print(ans)


t = int(input())
while t != 0:
	t -= 1
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	s = 0
	truth = 0
	for i in l:
		s = s + i
		if s >= n:
			break
		truth += 1
	print(truth)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	sum = 0
	t = 0
	try:
		for i in range(n):
			if sum + a[i] < n:
				sum += a[i]
				t += 1
			else:
				break
	except:
		pass
	print(t)


import math
for _ in range(int(input())):
	n1 = int(input())
	a = list(map(int, input().strip().split()))
	a.sort()
	s = 0
	si = 0
	for i in range(n1):
		if s + a[i] > n1 - 1:
			break
		si += 1
		s += a[i]
	print(si)


for i in range(int(input())):
	n = int(input())
	N = list(map(int, input().split()))
	child_i = 0
	truth_tellers = 0
	N.sort()
	for i in N:
		if child_i + i <= len(N) - 1:
			child_i += i
			truth_tellers += 1
	print(truth_tellers)


T = int(input(''))
for i in range(T):
	n = int(input(''))
	a = list(map(int, input('').strip().split()))
	a.sort()
	count = 0
	indeg0 = n - 1
	for x in a:
		if indeg0 >= x:
			indeg0 -= x
			count += 1
		else:
			break
	print(count)


for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split(' ')]
	arr.sort()
	temp = count = 0
	for i in arr:
		if temp + i < n:
			temp += i
			count += 1
		else:
			break
	print(count)


for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	track = 0
	count = 0
	for i in arr:
		if track + i <= n - 1:
			track += i
			count += 1
		else:
			break
	print(count)


t = int(input())
for i in range(t):
	j = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	total = 0
	count = 0
	for el in arr:
		if total + el <= j - 1:
			total += el
			count += 1
		else:
			break
	print(count)


def check(A, n):
	s = 0
	for (index, descendents) in enumerate(A):
		s += descendents
		if s > n - 1:
			return index
	if A[0] == 0:
		return n
	else:
		return n - 1
for i in range(int(input())):
	n = int(input())
	A = sorted(list(map(int, input().split())))
	print(check(A, n))


from math import gcd, sqrt, ceil, floor, log10, log2
from heapq import heapify, heappop, heappush, nsmallest, nlargest
from collections import Counter, deque, OrderedDict, defaultdict
from itertools import combinations, permutations, zip_longest
from bisect import bisect_left, bisect_right
from functools import lru_cache, reduce
import sys
import time
import string
import operator
RECURSION_LIMIT = int(10000000.0)
INT_MAX = float('inf')
INT_MIN = float('-inf')
MOD = int(10000000.0) + 9
NEWLINE = '\n'
SPACE = ' '
sys.setrecursionlimit(RECURSION_LIMIT)
inp = lambda fn: fn(input())
inp_vars = lambda fn, delim, convert_to=list: convert_to(map(fn, input().split(delim)))
enum = lambda itr, start: enumerate(itr, start)

def toposort(graph, n):
	degree = [0] * n
	for node in graph:
		for adj in graph[node]:
			degree[adj] += 1
	bfs_queue = [node for node in range(n) if not degree[node]]
	for node in bfs_queue:
		for adj in graph[node]:
			degree[adj] -= 1
			if not degree[adj]:
				bfs_queue.append(adj)
	return (bfs_queue, degree)

def dfs(graph, node, visited):
	visited.add(node)
	for adj in graph[node]:
		if adj in visited:
			continue
		dfs(graph, adj, visited)

def seive(n):
	is_prime = [True] * (n + 1)
	is_prime[0] = is_prime[1] = False
	for i in range(2, int(n ** 0.5) + 1):
		if is_prime[i]:
			for j in range(i * i, n + 1, i):
				is_prime[j] = False
	return is_prime[n]

def solve(*args, **kwargs):
	(n, arr) = args
	arr.sort()
	(res, flag) = (0, False)
	for ele in arr:
		if not flag:
			if ele + 1 <= n:
				res += 1
				n = n - ele - 1
			else:
				break
			flag = True
		elif ele <= n:
			n -= ele
			res += 1
		else:
			break
	return res

def main(*args, **kwargs):
	for _ in range(int(input())):
		arg1 = inp(int)
		arg3 = inp_vars(int, SPACE)
		res = solve(*(arg1, arg3))
		if type(res) in {list, tuple, set}:
			print(*res, sep='\n')
		else:
			print(res)
main()


a = int(input())
for i in range(a):
	N = int(input())
	A = list(map(int, input().split()))
	A.sort()
	y = 0
	x = 0
	for j in range(len(A)):
		y += A[j]
		if y >= N:
			x = j
			break
	if x == 0:
		if sum(A) >= N:
			print(N - 1)
		else:
			print(N)
	elif sum(A[:x + 1]) >= N:
		print(x)
	else:
		print(x + 1)


for i in range(int(input())):
	N = int(input())
	A = map(int, input().split())
	l1 = sorted(A)
	sum = 0
	c = 0
	for j in range(len(l1)):
		sum = sum + l1[j]
		c += 1
		if sum > N - 1:
			c = c - 1
			break
	print(c)


tn = int(input())
for _ in range(tn):
	n = int(input())
	sm = 0
	arr = list(map(int, input().split()))
	arr.sort()
	sm = sum(arr)
	nv = n
	while sm >= n:
		sm -= arr[nv - 1]
		nv -= 1
	print(nv)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	i = 1
	tt = 0
	for le in l:
		if i + le <= n:
			i += le
			tt += 1
	print(tt)


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)

def take_input(type='list-int'):
	if type == 'list-int':
		return list(map(int, input().split()))
	elif type == 'list-float':
		return list(map(float, input().split()))
	else:
		return None
for _ in range(int(input())):
	N = int(input())
	A = take_input()
	A = sorted(A)
	for i in range(N):
		N -= A[i]
		if N <= 0:
			i -= 1
			break
	print(i + 1)


def test():
	num_p = int(input())
	childrens_lst = list(map(int, input().split()))
	childrens_lst.sort()
	counter = 0
	Sum = 0
	for i in range(num_p):
		if Sum + childrens_lst[i] < num_p:
			counter += 1
			Sum += childrens_lst[i]
		else:
			break
	print(counter)
tests = int(input())
for i in range(tests):
	test()


def getMaxTruthTellers(case: list):
	nonConnectedNodes = len(case) - 1
	case.sort()
	truthTellers = 0
	for value in case:
		if value > nonConnectedNodes:
			break
		truthTellers += 1
		nonConnectedNodes -= value
	return truthTellers

def parseInput():
	T = int(input())
	testCases = []
	for i in range(T):
		N = int(input())
		testCases.append(list((int(x) for x in input().split())))
	return testCases

def main():
	testCases = parseInput()
	for case in testCases:
		print(getMaxTruthTellers(case))
main()


def function(A, N):
	A.sort()
	N = N - 1
	total = 0
	i = 0
	while i < len(A):
		total += A[i]
		if total > N:
			break
		i += 1
	return i

def main():
	T = int(input())
	for _ in range(T):
		N = int(input())
		A = list(map(int, input().split(' ')))
		val = function(A, N)
		print(val)
main()


tc = int(input())
for _ in range(tc):
	n = int(input())
	list1 = list(map(int, input().split()))
	list1.sort()
	sum = 0
	i = 0
	for i in range(n):
		sum += list1[i]
		if sum >= n:
			print(i)
			break
		if i == n - 1:
			print(n)


tc = int(input())
for _ in range(tc):
	n = int(input())
	list1 = list(map(int, input().split()))
	list1.sort()
	i = 0
	sons = 0
	while i < n and sons + list1[i] < n:
		sons = list1[i] + sons
		i = i + 1
	print(i)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = sum(l)
	l.sort()
	ans = n
	while s >= n:
		ans -= 1
		s -= l[-1]
		l.pop(-1)
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	claims = list(map(int, input().split()))
	claims.sort()
	included = 0
	sons_included = 0
	i = 0
	while i < n and sons_included + claims[i] < n:
		sons_included += claims[i]
		i += 1
		included += 1
	print(included)


for _ in range(int(input())):
	n = int(input())
	a = sorted(list(map(int, input().split())))
	(sum, i) = (0, 0)
	while sum < n and i < len(a):
		sum += a[i]
		i += 1
	if sum >= n:
		print(i - 1)
	else:
		print(i)


for _ in range(int(input())):
	n = int(input())
	a = sorted(map(int, input().split()))
	sum = 0
	count = 0
	for i in a:
		if sum + i > n - 1:
			break
		sum += i
		count += 1
	print(count)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	(i, ct, inc) = (0, 0, 0)
	while i < n and inc + a[i] < n:
		inc += a[i]
		i += 1
		ct += 1
	print(ct)


t = int(input())
for _ in range(t):
	n = int(input())
	count = 0
	ans = n
	l = list(map(int, input().split()))
	l.sort()
	for i in l:
		if ans - i > 0:
			ans -= i
			count += 1
	print(count)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	(i, cnt, inc) = (0, 0, 0)
	while i < n and inc + arr[i] < n:
		inc += arr[i]
		i += 1
		cnt += 1
	print(cnt)


for _ in range(int(input())):
	n = int(input())
	a = sorted(map(int, input().split()))
	s = c = 0
	for i in a:
		if s + i > n - 1:
			break
		s += i
		c += 1
	print(c)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	s = 0
	ans = 0
	for i in range(n):
		if s + arr[i] < n:
			s += arr[i]
			ans += 1
		else:
			break
	print(ans)


t = int(input())
while t > 0:
	n = int(input())
	a = [int(x) for x in input().split()]
	a.sort()
	res = 0
	s = 0
	for i in range(n):
		s += a[i]
		if s < n:
			res += 1
		else:
			break
	print(res)
	t -= 1


t = int(input())
for tc in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	rem = n - 1
	arr.sort()
	ans = 0
	for i in range(n):
		if arr[i] <= rem:
			ans += 1
			rem -= arr[i]
		else:
			break
	print(ans)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	count = 0
	b = n - 1
	for i in a:
		if b - i >= 0:
			b -= i
			count += 1
	print(count)