Matryoshka is a wooden toy in the form of a painted doll, inside which you can put a similar doll of a smaller size.

A set of nesting dolls contains one or more nesting dolls, their sizes are consecutive positive integers. Thus, a set of nesting dolls is described by two numbers: $s$ — the size of a smallest nesting doll in a set and $m$ — the number of dolls in a set. In other words, the set contains sizes of $s, s + 1, \dots, s + m - 1$ for some integer $s$ and $m$ ($s,m > 0$).

You had one or more sets of nesting dolls. Recently, you found that someone mixed all your sets in one and recorded a sequence of doll sizes — integers $a_1, a_2, \dots, a_n$.

You do not remember how many sets you had, so you want to find the minimum number of sets that you could initially have.

For example, if a given sequence is $a=[2, 2, 3, 4, 3, 1]$. Initially, there could be $2$ sets:

the first set consisting of $4$ nesting dolls with sizes $[1, 2, 3, 4]$;

a second set consisting of $2$ nesting dolls with sizes $[2, 3]$.

According to a given sequence of sizes of nesting dolls $a_1, a_2, \dots, a_n$, determine the minimum number of nesting dolls that can make this sequence.

Each set is completely used, so all its nesting dolls are used. Each element of a given sequence must correspond to exactly one doll from some set.


-----Input-----

The first line of input data contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The description of the test cases follows.

The first line of each test case contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the total number of matryoshkas that were in all sets.

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$)  — the sizes of the matryoshkas.

It is guaranteed that the sum of values of $n$ over all test cases does not exceed $2\cdot10^5$.


-----Output-----

For each test case, print one integer $k$ — the minimum possible number of matryoshkas sets.


-----Examples-----

Input
10
6
2 2 3 4 3 1
5
11 8 7 10 9
6
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
8
1 1 4 4 2 3 2 3
6
1 2 3 2 3 4
7
10 11 11 12 12 13 13
7
8 8 9 9 10 10 11
8
4 14 5 15 6 16 7 17
8
5 15 6 14 8 12 9 11
5
4 2 2 3 4
Output
2
1
6
2
2
2
2
2
4
3


-----Note-----

The first test case is described in the problem statement.

In the second test case, all matryoshkas could be part of the same set with minimum size $s=7$.

In the third test case, each matryoshka represents a separate set.

Source: codeforces | Difficulty: EASY
Tags: Sorting

Data structures

Greedy algorithms


Solutions:
def tests(t):
	for i in range(t):
		n = input()
		a = input()
		b = [int(i) for i in a.split()]
		b.sort()
		n_actual = b[0]
		cant_matro = 1
		cant_actual = 1
		cant_ant = 0
		for i in range(1, len(b)):
			if b[i] == n_actual:
				cant_actual = cant_actual + 1
				if cant_ant > 0:
					cant_ant = cant_ant - 1
				else:
					cant_matro = cant_matro + 1
			elif b[i] == n_actual + 1:
				n_actual = b[i]
				cant_ant = cant_actual - 1
				cant_actual = 1
			else:
				n_actual = b[i]
				cant_matro = cant_matro + 1
				cant_actual = 1
				cant_ant = 0
		print(cant_matro)
t = int(input())
tests(t)


n = int(input())
for i in range(n):
	nn = int(input())
	lista = [int(i) for i in input().split()]
	contador = 0
	lista = sorted(lista)
	ultimo_n = lista[0]
	tope = 0
	cuantos_n = 0
	for i in lista:
		if i == ultimo_n:
			cuantos_n += 1
			if cuantos_n > tope:
				contador += 1
		elif i == ultimo_n + 1:
			tope = cuantos_n
			cuantos_n = 1
			ultimo_n = i
		else:
			tope = 0
			cuantos_n = 1
			ultimo_n = i
			contador += 1
	print(contador)


for s in [*open(0)][2::2]:
	r = p = l = 0
	for x in sorted(map(int, s.split())):
		if x > p:
			m = l * (x - p < 2)
			l = 0
		l += 1
		r += l > m
		p = x
	print(r)


import sys
from math import *
from collections import defaultdict, deque
input = sys.stdin.readline
mod = 10 ** 9 + 7
INF = 1061109567
N = int(2 * 10 ** 5 + 5)
LINF = 4557430888798830399

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	(ans, idxl) = (0, 0)
	(cnt1, cnt2) = (0, 0)
	num1 = a[0] - 2
	for i in range(n):
		if a[i] == a[idxl]:
			cnt2 += 1
		else:
			if num1 == a[i - 1] - 1:
				if cnt2 > cnt1:
					ans += cnt2 - cnt1
			else:
				ans += cnt2
			cnt1 = cnt2
			cnt2 = 1
			idxl = i
			num1 = a[i - 1]
	if num1 == a[idxl] - 1:
		if cnt2 > cnt1:
			ans += cnt2 - cnt1
	else:
		ans += cnt2
	print(ans)
T = int(input())
for t in range(T):
	solve()


from heapq import heappop, heappush, heapify
import sys
input = lambda : sys.stdin.readline().strip()

def solve():
	n = int(input())
	l = [int(i) for i in input().split()]
	l = sorted(l)
	h = []
	tot = 0
	for i in l:
		while h and h[0] + 1 < i:
			heappop(h)
			tot += 1
		if h and h[0] == i:
			heappush(h, i)
		elif h and h[0] + 1 == i:
			heappop(h)
			heappush(h, i)
		else:
			heappush(h, i)
	print(len(h) + tot)
for i in range(int(input())):
	solve()


from math import gcd
from sys import setrecursionlimit
setrecursionlimit(10 ** 6)

def ye():
	print('Yes')

def no():
	print('NO')

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	su = 0
	now = 0
	fl = 0
	now2 = 0
	for i in range(1, n):
		if a[i] == a[i - 1] + 1:
			if now2 > now:
				su += now2 - now
			now2 = now
			now = 0
		elif a[i] == a[i - 1]:
			now += 1
		else:
			su += max(now2, now) + 1
			now = 0
			fl = 0
			now2 = 0
	su += max(now, now2) + 1
	print(su)
	return
TT_T = int(input())
while TT_T:
	solve()
	TT_T -= 1


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	arr.sort()
	p = 0
	temp = -2
	ans = 0
	c = 0
	for x in range(n):
		if arr[x] != temp + 1:
			if arr[x] == temp:
				c += 1
			else:
				if c - p > 0:
					ans += c - p
				c = 0
				p = 0
				ans += 1
		else:
			if c - p > 0:
				ans += c - p
			p = c
			c = 0
		temp = arr[x]
	if c - p > 0:
		ans += c - p
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	(*a,) = map(int, input().split())
	a.sort()
	a += [-1]
	last = -1
	tek = a[0]
	kol_tek = 0
	kol_Last = 0
	ans = 0
	for i in a:
		if i == tek:
			kol_tek += 1
		elif tek == last + 1:
			ans += max(0, kol_tek - kol_Last)
			last = tek
			tek = i
			kol_Last = kol_tek
			kol_tek = 1
		else:
			ans += kol_tek
			last = tek
			tek = i
			kol_Last = kol_tek
			kol_tek = 1
	print(ans)


from collections import deque
for _ in range(int(input())):
	n = int(input())
	a = sorted(map(int, input().split()))
	count = 0
	sets = deque()
	for ai in a:
		while len(sets) > 0:
			p = sets.popleft()
			if p == ai - 1:
				break
			if p == ai:
				sets.appendleft(p)
				break
			count += 1
		sets.append(ai)
	count += len(sets)
	print(count)


def ghg(a: list):
	a.sort()
	d = dict()
	for i in a:
		d[i] = d.get(i, 0) + 1
	v = 0
	p = 0
	p2 = 0
	for i in d.items():
		if p:
			if p + 1 != i[0]:
				p2 = 0
		if i[1] > p2:
			v += i[1] - p2
		p = i[0]
		p2 = i[1]
	return v
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(ghg(a))


from heapq import heappop, heappush, heapify
import sys
input = lambda : sys.stdin.readline().strip()

def lst():
	return [int(i) for i in input().split()]
mm = int(input())
for i in range(mm):
	nn = int(input())
	ll = lst()
	ll = sorted(ll)
	hh = []
	tot = 0
	for i in ll:
		while hh and hh[0] + 1 < i:
			heappop(hh)
			tot += 1
		if hh and hh[0] == i:
			heappush(hh, i)
		elif hh and hh[0] + 1 == i:
			heappop(hh)
			heappush(hh, i)
		elif hh:
			heappop(hh)
			heappush(hh, i)
			tot += 1
		else:
			heappush(hh, i)
	print(str(len(hh) + tot))


from collections import defaultdict as dd
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = dd(int)
	ans = 0
	a.sort()
	for num in a:
		if d[num - 1]:
			d[num - 1] -= 1
		d[num] += 1
	print(sum(d.values()))


t = int(input())
for i in range(t):
	n = int(input())
	res = sorted(list(map(int, input().split())))
	d = dict()
	for j in res:
		if j not in d:
			d[j] = 0
		d[j] += 1
		if j - 1 in d and d[j - 1] != 0:
			d[j - 1] -= 1
	print(sum(d.values()))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	d = {}
	for i in arr:
		if i not in d:
			d[i] = 0
		if i - 1 in d:
			if d[i - 1] == 1:
				del d[i - 1]
			else:
				d[i - 1] -= 1
			d[i] += 1
		else:
			d[i] += 1
	ans = 0
	for i in d.keys():
		ans += d[i]
	print(ans)


from collections import Counter as cs
for _ in range(int(input())):
	n = int(input())
	l1 = [int(a) for a in input().split()]
	l1.sort()
	d1 = dict(cs(l1))
	fq = 0
	ans = 0
	ls = l1[0] - 1
	for i in d1:
		if i != ls + 1:
			ans += fq
		elif fq > d1[i]:
			ans += max(0, fq - d1[i])
		fq = d1[i]
		ls = i
	print(ans + fq)


for a in range(int(input())):
	n = int(input())
	ar = list(map(int, input().split()))
	ar.sort()
	(count, curCount, prevCount) = (0, 1, 0)
	ar.append(ar[-1] + 1)
	for b in range(1, n + 1):
		if ar[b - 1] != ar[b]:
			if curCount > prevCount:
				count += curCount - prevCount
			(prevCount, curCount) = (curCount, 1) if ar[b - 1] + 1 == ar[b] else (0, 1)
		else:
			curCount += 1
	print(count)


import sys
input = sys.stdin.readline

def solve_d():
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	answ = 0
	my_dict = {}
	for i in range(n):
		if arr[i] not in my_dict:
			my_dict[arr[i]] = 1
		else:
			my_dict[arr[i]] += 1
	chains = list(my_dict.keys())
	chains.sort()
	ln = len(chains)
	i = 0
	while i < ln:
		j = i + 1
		key1 = chains[i]
		if j < ln and key1 + 1 == chains[j]:
			key2 = key1 + 1
			val1 = my_dict[key1]
			val2 = my_dict[key2]
			if val1 < val2:
				i += 1
				continue
			else:
				answ += val1 - val2
		else:
			answ += my_dict[key1]
		i += 1
	return answ

def main():
	for _ in range(int(input())):
		answ = solve_d()
		print(answ)
main()


for s in [*open(0)][2::2]:
	d = {}
	r = 0
	for x in sorted(map(int, s.split())):
		if d.get(x - 1):
			d[x - 1] -= 1
		else:
			r += 1
		d[x] = d.get(x, 0) + 1
	print(r)


from itertools import *
for s in [*open(0)][2::2]:
	a = [(k, len([*g])) for (k, g) in groupby(sorted(map(int, s.split())))]
	print(sum((max(0, y - (v - u < 2) * x) for ((u, x), (v, y)) in zip([(0, 0)] + a, a))))


def solve(a):
	seq = []
	curseq = []
	a.sort()
	last = -1
	seqidx = 0
	for v in a:
		if v == last:
			seqidx += 1
			if seqidx == len(curseq):
				curseq.append(len(seq))
				seq.append([v])
			else:
				seq[curseq[seqidx]].append(v)
		elif v == last + 1:
			if seqidx + 1 < len(curseq):
				curseq[seqidx + 1:] = []
			seqidx = 0
			seq[curseq[seqidx]].append(v)
		else:
			curseq = []
			curseq.append(len(seq))
			seq.append([v])
			seqidx = 0
		last = v
	return len(seq)
t = int(input())
ans = []
for ti in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	ans.append(solve(a))
for a in ans:
	print(a)


cases = int(input())
for case in range(cases):
	n = int(input())
	dolls = sorted(map(int, input().split()))
	c = 0
	v = -1
	while dolls:
		if dolls[-1] != v - 1:
			prev = 0
		v = dolls[-1]
		current = 0
		while dolls and dolls[-1] == v:
			dolls.pop()
			current += 1
			if prev:
				prev -= 1
			else:
				c += 1
		prev = current
	print(c)


for _ in range(int(input())):
	n = int(input())
	arr = sorted(map(int, input().split()))
	counts = {}
	for i in arr:
		if i - 1 not in counts or counts[i - 1] == 0:
			counts[i] = counts.get(i, 0) + 1
		else:
			counts[i - 1] -= 1
			counts[i] = counts.get(i, 0) + 1
	print(sum(counts.values()))


for j in range(int(input())):
	t = int(input())
	g = list(map(int, input().split()))
	k = {}
	g.sort()
	for j in g:
		if j in k:
			k[j] += 1
		else:
			k[j] = 1
	m = [*k]
	v = [*k.values()]
	c = v[0]
	if len(m) == 1:
		print(v[0])
	else:
		for i in range(1, len(m)):
			if m[i] - m[i - 1] == 1:
				if v[i] - v[i - 1] > 0:
					c += v[i] - v[i - 1]
			else:
				c += v[i]
		print(c)


from itertools import groupby
for _ in range(int(input())):
	input()
	sets = []
	for (key, group) in groupby(sorted(map(int, input().split()))):
		for (i, j) in enumerate(group):
			if i + 1 > len(sets):
				break
			if sets[-i - 1] == key - 1:
				sets[-i - 1] += 1
			else:
				break
		else:
			continue
		sets.extend(group)
		sets.append(key)
	print(len(sets))


from collections import Counter
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	l2 = []
	d = Counter(l)
	k = list(d.keys())
	v = list(d.values())
	c = v[0]
	for i in range(1, len(k)):
		if k[i] == k[i - 1] + 1:
			c += max(0, v[i] - v[i - 1])
		else:
			c += v[i]
	print(c)


t = int(input())
for i in range(t):
	n = int(input())
	w = list(map(int, input().split()))
	w.sort()
	i = 0
	last = 0
	ans = 0
	lastl = 0
	while i < n:
		j = i
		while j + 1 < n and w[j + 1] == w[j]:
			j += 1
		length = j - i + 1
		if w[j] - 1 == lastl:
			if length > last:
				ans += length - last
			last = length
			lastl = w[j]
		else:
			ans += length
			lastl = w[j]
			last = length
		i = j + 1
	print(ans)


import collections
T = int(input())
while T > 0:
	n = int(input())
	A = list(map(int, input().split()))
	A.sort()
	dic = collections.defaultdict(int)
	ret = 0
	for i in A:
		if dic[i - 1] == 0:
			ret += 1
		else:
			dic[i - 1] -= 1
		dic[i] += 1
	print(ret)
	T -= 1


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	d = defaultdict(int)
	cnt = 0
	arr.sort()
	for i in range(n):
		d[arr[i]] += 1
		if d[arr[i] - 1] > 0:
			d[arr[i] - 1] -= 1
		else:
			cnt += 1
	print(cnt)


from math import gcd
t = int(input())
for p in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	i = 0
	ans = 0
	maxim = 0
	while i != n:
		cnt = 1
		while i + 1 < n and a[i + 1] == a[i]:
			i += 1
			cnt += 1
		if cnt < maxim:
			ans += maxim - cnt
			maxim = cnt
		else:
			maxim = cnt
		if i + 1 < n and a[i + 1] == a[i] + 1:
			i += 1
		else:
			i += 1
			ans += maxim
			maxim = 0
	print(ans)


t = int(input())
for t1 in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	i = 0
	while i < n and a[i] == a[0]:
		i += 1
	cnt = i
	ans = cnt
	while i < n:
		if a[i] > a[i - 1] + 1:
			cnt = 0
		tmp = 0
		x = a[i]
		while i < n and a[i] == x:
			tmp += 1
			i += 1
		if tmp > cnt:
			ans += tmp - cnt
		cnt = tmp
	print(ans)


for tcase in range(int(input())):
	n = int(input())
	a = sorted(map(int, input().split()))
	(x, y) = ([a[0]], [1])
	for ai in a[1:]:
		if ai == x[-1]:
			y[-1] += 1
		else:
			x.append(ai)
			y.append(1)
	ans = y[0]
	for i in range(1, len(x)):
		if x[i] - x[i - 1] == 1:
			ans += max(0, y[i] - y[i - 1])
		else:
			ans += max(0, y[i])
	print(ans)


for _ in range(int(input())):
	n = int(input())
	arr = [int(el) for el in input().split()]
	arr.sort()
	(ans, cur_ans, i) = (0, 1, 1)
	while i < n:
		j = i - 1
		while i < n and arr[i] == arr[j]:
			i += 1
		if i >= n:
			cur_ans = max(cur_ans, i - j)
			break
		if cur_ans > i - j:
			ans += cur_ans - i + j
		cur_ans = i - j
		if arr[i] - arr[j] > 1:
			ans += cur_ans
			cur_ans = 1
		i += 1
	ans += cur_ans
	print(ans)


from collections import Counter
from math import *

def lstStrRd():
	return list(input())

def intRd():
	return int(input())

def lstRd():
	return list(map(int, input().split()))
for _ in range(intRd()):
	n = intRd()
	a = sorted(lstRd())
	cnt = Counter(a)
	temp = cnt[a[0]]
	last = a[0]
	res = 0
	for i in sorted(set(a))[1:]:
		if i - 1 != last:
			res += temp
			temp = cnt[i]
		elif cnt[i] >= temp:
			temp = cnt[i]
		else:
			res += temp - cnt[i]
			temp = cnt[i]
		last = i
	print(res + temp)


from collections import defaultdict

def minimum_dolls(n, arr):
	arr.sort()
	dict = defaultdict(lambda : 0)
	for i in range(n):
		dict[arr[i]] += 1
	count = 0
	temp = list(dict.keys())
	for i in range(len(temp)):
		if dict[temp[i]] - dict[temp[i] - 1] > 0:
			count += dict[temp[i]] - dict[temp[i] - 1]
	print(count)

def main():
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().split()))
		minimum_dolls(n, arr)
main()


def solution(n, arr):
	arr.sort()
	visit = {}
	res = [0]
	k = 0
	for i in range(n):
		if i > 0 and arr[i] > arr[i - 1] + 1:
			res.append(0)
			k += 1
		if arr[i] not in visit:
			visit[arr[i]] = 1
			j = i + 1
			while j < n and arr[j] == arr[i]:
				visit[arr[i]] += 1
				j += 1
			if res[k] != 0 and arr[i - 1] in visit and (visit[arr[i]] > visit[arr[i - 1]]):
				res[k] += visit[arr[i]] - visit[arr[i - 1]]
			elif res[k] == 0:
				res[k] += visit[arr[i]]
	print(sum(res))
	return
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	solution(n, arr)


for _ in range(int(input())):
	N = int(input())
	M = sorted(list(map(int, input().split())))
	quantity = {}
	sizes = []
	last = -1
	for m in M:
		if last != m:
			sizes.append(m)
			quantity[m] = 1
		else:
			quantity[m] += 1
		last = m
	ans = quantity[sizes[0]]
	for i in range(1, len(sizes)):
		if sizes[i - 1] == sizes[i] - 1:
			ans += max(0, quantity[sizes[i]] - quantity[sizes[i - 1]])
		else:
			ans += quantity[sizes[i]]
	print(ans)


from collections import Counter

def main():
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	st = set(arr)
	st = list(st)
	st.sort()
	freq = Counter(arr)
	ans = 0
	curr = freq[st[0]]
	for i in range(1, len(st)):
		if st[i] == st[i - 1] + 1:
			if freq[st[i]] >= curr:
				curr = freq[st[i]]
				continue
			ans += curr - freq[st[i]]
			curr = freq[st[i]]
		else:
			ans += curr
			curr = freq[st[i]]
	ans += curr
	print(ans)
	return
for _ in range(int(input())):
	main()


import sys
import math
import heapq
import bisect
t = int(input())
for _ in range(t):
	n = int(input())
	l = [int(x) for x in input().split()]
	l.sort()
	d = {}
	for i in l:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	ans = 1
	check = l[0]
	i = 1
	while i < n:
		if l[i] == check + 1:
			temp = l[i]
			while d[check] > 0 and l[i] == temp:
				d[check] -= 1
				i += 1
				if i == n:
					break
			else:
				check = temp
		elif l[i] == check:
			ans += 1
			i += 1
		else:
			check = l[i]
			ans += 1
			i += 1
	print(ans)


n = int(input())
for _ in range(n):
	m = int(input())
	vals = sorted(map(int, input().split()))
	occ = {}
	for x in vals:
		occ[x] = occ.get(x, 0) + 1
	keys = sorted(occ.keys())
	res = occ[keys[0]]
	to_suppr = occ[keys[0]]
	j = 1
	while j < len(keys):
		i = keys[j]
		if i != keys[j - 1] + 1:
			to_suppr = 0
		if occ[i] > to_suppr:
			res += occ[i] - to_suppr
			to_suppr += occ[i] - to_suppr
		else:
			to_suppr = occ[i]
		j += 1
	print(res)


from collections import defaultdict

def N():
	return int(input())

def A():
	return [int(x) for x in input().split()]

def S():
	return input()
for _ in range(N()):
	n = N()
	d = {}
	if 'codeforces' == 28226329:
		print('Tanmay')
	c = 0
	a = A()
	a.sort()
	for i in a:
		if i - 1 in d.keys():
			if d[i - 1] - 1 < 0:
				del d[i - 1]
			else:
				d[i - 1] = d[i - 1] - 1
		d[i] = d.get(i, 0) + 1
	for i in d.keys():
		c += d[i]
	print(c)


def func():
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	ans = 0
	d = 0
	v = []
	for i in range(0, n):
		d += 1
		if i == n - 1 or l[i + 1] != l[i]:
			v.append([l[i], d])
			d = 0
	ans = v[0][1]
	d = v[0][1]
	for i in range(1, len(v)):
		if v[i][0] > v[i - 1][0] + 1:
			ans += v[i][1]
			d = v[i][1]
			continue
		if v[i][1] > d:
			ans += v[i][1] - d
		d = v[i][1]
	print(ans)
for i in range(int(input())):
	func()


tests = int(input())
count = 0
for _ in range(tests):
	total = int(input())
	sizes = list(map(int, input().split()))
	sizes.sort()
	frequencies = [[sizes[0], 1]]
	for x in sizes[1:]:
		if frequencies[-1][0] == x:
			frequencies[-1][1] += 1
		else:
			frequencies.append([x, 1])
	result = 0
	(size, height) = (frequencies[0][0], frequencies[0][1])
	for x in frequencies[1:]:
		if x[0] == size + 1:
			if x[1] < height:
				result += height - x[1]
			height = x[1]
			size += 1
		else:
			result += height
			(size, height) = (x[0], x[1])
	result += height
	print(result)


t = int(input())
for _ in range(t):
	n = int(input())
	a = sorted(map(int, input().split()))
	total = 0
	i = 0
	prev = 0
	while i < len(a):
		j = i + 1
		while j < len(a) and a[i] == a[j]:
			j += 1
		total += max(0, j - i - prev)
		prev = j - i if j < len(a) and a[i] == a[j] - 1 else 0
		i = j
	print(total)


t = int(input())
from collections import Counter
while t:
	n = int(input())
	li = list(map(int, input().strip().split()))
	li.sort()
	di = Counter(li)
	li = sorted(set(li))
	li = li[::-1]
	ans = di[li[0]]
	for i in range(1, len(li)):
		v = di[li[i]]
		if li[i - 1] - li[i] <= 1:
			v1 = di[li[i - 1]]
			v2 = di[li[i]]
			if v1 < v2:
				ans += v2 - v1
		else:
			ans += v
	print(ans)
	t -= 1


import math
T = int(input(''))
for i in range(T):
	n = int(input())
	str1 = input()
	l1 = [int(c) for c in str1.split()]
	l1.sort()
	hashDict = {}
	for element in l1:
		if element not in hashDict:
			hashDict[element] = 1
		else:
			hashDict[element] += 1
	l1 = list(set(l1))
	l1.sort()
	dollCount = hashDict[l1[0]]
	for j in range(1, len(l1)):
		if l1[j] - l1[j - 1] > 1:
			dollCount += hashDict[l1[j]]
		else:
			x = hashDict[l1[j]] - hashDict[l1[j] - 1]
			if x > 0:
				dollCount += x
	print(dollCount)


def mini_dolls(n, l):
	l.sort()
	d = []
	last = l[0]
	c = 1
	ans = 0
	for i in range(1, n):
		if l[i] == last:
			c += 1
		else:
			d.append([last, c])
			c = 1
			last = l[i]
	d.append([last, c])
	while True:
		prev = d[0][0]
		d[0][1] -= 1
		i = 1
		if i == len(d):
			ans += 1
		d2 = []
		if d[0][1] != 0:
			d2.append(d[0])
		while i < len(d):
			if d[i][0] == prev + 1:
				d[i][1] -= 1
				prev = d[i][0]
				if d[i][1] != 0:
					d2.append(d[i])
				i += 1
				if i == len(d):
					ans += 1
			else:
				ans += 1
				prev = d[i][0]
				d[i][1] -= 1
				if d[i][1] != 0:
					d2.append(d[i])
				i += 1
				if i == len(d):
					ans += 1
		d = d2
		if len(d2) == 0:
			break
	return ans
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	print(mini_dolls(n, l))


input = __import__('sys').stdin.readline
for _ in range(int(input())):
	n = int(input())
	arr = sorted([*map(int, input().split())])
	sorted_val = []
	val = [arr[0], 1]
	for i in range(1, n):
		if val[0] == arr[i]:
			val[1] += 1
		else:
			sorted_val.append(val)
			val = [arr[i], 1]
	sorted_val.append(val)
	ans = 0
	value = -1
	prev_length = 0
	for (x, c) in sorted_val:
		if x == value + 1:
			value = x
			if prev_length > c:
				ans += prev_length - c
			prev_length = c
		else:
			value = x
			ans += prev_length
			prev_length = c
	else:
		ans += prev_length
	print(ans)


from math import gcd
from sys import setrecursionlimit
setrecursionlimit(10 ** 6)
from operator import itemgetter

def ye():
	print('Yes')

def no():
	print('NO')

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	indexs = [index for (index, value) in sorted(enumerate(a), key=itemgetter(1))]
	a.sort()
	su = 0
	now = 0
	fl = 0
	now2 = 0
	for i in range(1, n):
		if a[i] == a[i - 1] + 1:
			if now2 > now:
				su += now2 - now
			now2 = now
			now = 0
		elif a[i] == a[i - 1]:
			now += 1
		else:
			su += max(now2, now) + 1
			now = 0
			fl = 0
			now2 = 0
	su += max(now, now2) + 1
	print(su)
	return
TT_T = int(input())
while TT_T:
	solve()
	TT_T -= 1


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split(' ')))
	l.sort()
	mp = {}
	arr = []
	for i in l:
		if i in mp:
			mp[i] += 1
		else:
			mp[i] = 1
			arr.append(i)
	if len(arr) == 1:
		print(mp[l[0]])
	else:
		ans = mp[arr[0]]
		for i in range(1, len(arr)):
			if arr[i] - 1 in mp:
				if mp[arr[i] - 1] < mp[arr[i]]:
					ans = ans + mp[arr[i]] - mp[arr[i] - 1]
			else:
				ans = ans + mp[arr[i]]
		print(ans)


from collections import Counter

def solve():
	n = int(input())
	a = [int(x) for x in input().split()]
	a.sort()
	cnt = Counter(a)
	res = 0
	for (v, c) in cnt.items():
		j = v
		if c > 0:
			res += c
			while cnt[j] > 0:
				t = cnt[j]
				cnt[j] -= c
				c = min(t, c)
				j += 1
	print(res)
	return
t = int(input())
for _ in range(t):
	solve()


t = int(input())
for i in range(t):
	n = int(input())
	a = input().split()
	for j in range(n):
		a[j] = int(a[j])
	a.sort()
	mem = [[1]]
	count = 0
	for j in range(1, n):
		if a[j] == a[j - 1]:
			mem[-1][-1] += 1
		elif a[j] == a[j - 1] + 1:
			mem[-1].append(1)
		else:
			mem.append([1])
	for j in range(len(mem)):
		count += mem[j][0]
		for k in range(1, len(mem[j])):
			if mem[j][k] > mem[j][k - 1]:
				count += mem[j][k] - mem[j][k - 1]
	print(count)


from collections import defaultdict
import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	check = defaultdict(lambda : 0)
	for num in a:
		check[num] += 1
	dic = []
	for num in check:
		dic.append((num, check[num]))
	res = dic[0][1]
	for i in range(1, len(dic)):
		if dic[i][0] == dic[i - 1][0] + 1:
			res += max(0, dic[i][1] - dic[i - 1][1])
		else:
			res += dic[i][1]
	print(res)


from collections import defaultdict
t = int(input())
for _ in range(int(t)):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	check = defaultdict(lambda : 0)
	for num in a:
		check[num] += 1
	data = []
	for num in check:
		data.append((num, check[num]))
	res = data[0][1]
	for i in range(1, len(data)):
		if data[i][0] == data[i - 1][0] + 1:
			res += max(0, data[i][1] - data[i - 1][1])
		else:
			res += data[i][1]
	print(res)


for _ in range(int(input())):
	n = int(input())
	arr2 = sorted(list(map(int, input().split())))
	if n == 1:
		print(1)
		continue
	p = arr2[0]
	count = 1
	arr1 = []
	for x in range(1, n):
		if arr2[x] == p:
			count += 1
			if x == n - 1:
				arr1.append([arr2[x], count])
		else:
			arr1.append([arr2[x - 1], count])
			count = 1
			p = arr2[x]
			if x == n - 1:
				arr1.append([arr2[x], count])
	arr = sorted(arr1, key=lambda xx: (xx[0], xx[1]), reverse=True)
	if len(arr) == 1:
		print(arr[0][1])
		continue
	tmp_max = arr[0][1]
	prev_size = arr[0][0]
	out = arr[0][1]
	for x in range(1, len(arr)):
		if prev_size - arr[x][0] == 1:
			if arr[x][1] > tmp_max:
				out += arr[x][1] - tmp_max
				tmp_max = arr[x][1]
			elif arr[x][1] < tmp_max:
				tmp_max = arr[x][1]
			prev_size = arr[x][0]
		else:
			out += arr[x][1]
			tmp_max = arr[x][1]
			prev_size = arr[x][0]
	print(out)


T = int(input())
for t in range(T):
	n = int(input())
	a = sorted(list(map(int, input().split())))
	k = 0
	p = 1
	t = 1
	for i in range(1, len(a)):
		if a[i] == a[i - 1]:
			t += 1
		elif a[i] - a[i - 1] == 1:
			if t > p:
				p = t
			if t < p:
				k += p - t
				p = t
			t = 1
		else:
			if t >= p:
				p = t
			k += p
			p = 1
			t = 1
	if t > p:
		p = t
	k += p
	print(k)


t = int(input())
for i in range(t):
	cnt = {}
	n = int(input())
	lst = list(map(int, input().split()))
	for i in lst:
		if str(i) not in cnt.keys():
			cnt[str(i)] = 1
		else:
			cnt[str(i)] += 1
	lst2 = list(set(lst))
	lst2.sort()
	res = cnt[str(lst2[0])]
	cur_flow = res
	for i in range(1, len(lst2)):
		if lst2[i - 1] != lst2[i] - 1:
			cur_flow = cnt[str(lst2[i])]
			res += cur_flow
		else:
			tmp = cnt[str(lst2[i])]
			res += max(tmp - cur_flow, 0)
			cur_flow = tmp
	print(res)


t = int(input())
for i in range(0, t):
	m = int(input())
	n = list(map(int, input().split()))
	n.sort()
	l = []
	ll = []
	for j in range(0, m):
		l.append([])
		ll.append([])
	l[0].append(n[0])
	ll[0].append(1)
	seq = 0
	pos = 0
	for j in range(1, m):
		if n[j] == n[j - 1]:
			ll[seq][pos] = ll[seq][pos] + 1
		elif n[j] == n[j - 1] + 1:
			pos = pos + 1
			l[seq].append(n[j])
			ll[seq].append(1)
		else:
			seq = seq + 1
			pos = 0
			l[seq].append(n[j])
			ll[seq].append(1)
	ans = seq + 1
	xx = 0
	xprev = 1
	for z in range(0, ans):
		for q in range(0, len(ll[z])):
			xx = ll[z][q]
			if xx > xprev:
				ans = ans + xx - xprev
				xprev = xx
			elif xx < xprev:
				xprev = xx
		xx = 0
		xprev = 1
	print(ans)


t = int(input())
for test in range(t):
	n = int(input())
	cnt = [[0, 0]] * (n + 5)
	d = {}
	a = list(map(int, input().split()))
	a.sort()
	gg = max(a)
	last = -1
	next = 0
	for i in range(n):
		if a[i] == last:
			cnt[d[a[i]]][1] += 1
		else:
			d[a[i]] = next
			next += 1
			cnt[d[a[i]]] = [a[i], 1]
		last = a[i]
	otv = n
	cur = 0
	q = 0
	while q < n:
		x = d[a[q]]
		if cnt[x][1] != 0:
			for i in range(x, n):
				if cnt[i][1] > 0:
					cur += 1
					cnt[i][1] -= 1
					if cnt[i + 1][0] - cnt[i][0] != 1:
						break
				else:
					break
			otv -= cur - 1
			cur = 0
		q += 1
	print(otv)


import sys
from collections import Counter
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	c = Counter(a)
	ans = 0
	B = sorted(set(a))
	for b in B:
		if c[b] > c[b - 1]:
			ans += c[b] - c[b - 1]
	print(ans)


answer = []
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	hm = {}
	for i in arr:
		hm[i] = 0
	for i in arr:
		if i - 1 in hm and hm[i - 1] > 0:
			hm[i - 1] -= 1
		hm[i] += 1
	ans = 0
	for i in hm:
		ans += hm[i]
	answer.append(ans)
for i in answer:
	print(i)


for i in range(int(input())):
	input()
	lst = [int(x) for x in input().split()]
	lst.sort()
	d = {x: 0 for x in lst}
	kits = 0
	for n in lst:
		if n - 1 not in d or not d[n - 1]:
			kits += 1
		else:
			d[n - 1] -= 1
		d[n] += 1
	print(kits)


op = []
for i in range(int(input())):
	input()
	lst = [int(j) for j in input().split()]
	lst.sort()
	nums = {j: 0 for j in lst}
	threads = 0
	for j in lst:
		if j - 1 not in nums or not nums[j - 1]:
			threads += 1
		else:
			nums[j - 1] -= 1
		nums[j] += 1
	op.append(str(threads))
print('\n'.join(op))


import math
from random import randint
RANDOM = randint(1, 10 ** 9)

class Wrapper(int):

	def __init__(self, x):
		int.__init__(x)

	def __hash__(self):
		return super(Wrapper, self).__hash__() ^ RANDOM

def main():
	t = int(input())
	for _ in range(t):
		res = alg()
		print(res)

def alg():
	n = int(input())
	aDict = dict()
	res = 0
	for i in input().split():
		i = Wrapper(int(i))
		if not i in aDict:
			aDict[i] = 0
		aDict[i] += 1
	for k in aDict:
		k = Wrapper(k)
		kprev = Wrapper(k - 1)
		if kprev in aDict:
			res += max(0, aDict[k] - aDict[kprev])
		else:
			res += aDict[k]
	return res
main()


from random import randint
RANDOM = randint(1, 10 ** 9)

class Wrapper(int):

	def __init__(self, x):
		int.__init__(x)

	def __hash__(self):
		return super(Wrapper, self).__hash__() ^ RANDOM

def solve(vals):
	counter = {}
	for item in vals:
		cur = Wrapper(item)
		if cur in counter:
			counter[cur] += 1
		else:
			counter[cur] = 1
	all_options = [(cost, num) for (cost, num) in sorted(counter.items())]
	num_of_sets = all_options[0][1]
	for i in range(1, len(all_options)):
		if all_options[i][0] - all_options[i - 1][0] != 1:
			num_of_sets += all_options[i][1]
		else:
			diff = all_options[i][1] - all_options[i - 1][1]
			if diff > 0:
				num_of_sets += diff
	return num_of_sets
n = int(input())
for j in range(n):
	length = int(input())
	vals = [int(_) for _ in input().split()]
	print(solve(vals))


import math
from random import randint
RANDOM = randint(1, 10 ** 9)

class Wrapper(int):

	def __init__(self, x):
		int.__init__(x)

	def __hash__(self):
		return super(Wrapper, self).__hash__() ^ RANDOM
t = int(input())
for _ in range(0, t):
	n = int(input())
	list1 = [int(num) for num in input().split()]
	dict1 = {}
	for num in list1:
		num = Wrapper(num)
		if num not in dict1:
			dict1[num] = 0
		dict1[num] += 1
	c = 0
	for key in dict1:
		key = Wrapper(key)
		kless = Wrapper(key - 1)
		if kless not in dict1:
			c += dict1[key]
		elif dict1[kless] <= dict1[key]:
			c += dict1[key] - dict1[kless]
	print(c)