D. Матрёшки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Матрёшка — деревянная игрушка в виде расписной куклы, внутрь которой можно вложить подобную ей куклу меньшего размера.

Набор матрёшек содержит одну или более матрёшку, их размеры составляют подряд идущие положительные целые числа. Таким образом, набор матрёшек описывается двумя числами: $$$s$$$ — размером минимальной матрёшки в наборе и $$$m$$$ — количеством матрёшек в наборе. Иными словами, набор содержит матрёшки размеров $$$s, s + 1, \dots, s + m - 1$$$ для некоторых целых $$$s$$$ и $$$m$$$ ($$$s,m > 0$$$).

У вас было несколько наборов матрёшек. Недавно вы обнаружили, что кто-то смешал все ваши наборы в один и записал последовательность размеров кукол — целые числа $$$a_1, a_2, \dots, a_n$$$.

Вы не помните, сколько точно у вас было наборов, поэтому хотите найти минимальное количество наборов, которое могло быть у вас изначально.

Например, если заданная последовательность имеет вид $$$a=[2, 2, 3, 4, 3, 1]$$$. Изначально могло быть всего $$$2$$$ набора:

  • первый набор, состоящий из $$$4$$$-х матрешек с размерами $$$[1, 2, 3, 4]$$$;
  • второй набор, состоящий из $$$2$$$-x матрешек с размерами $$$[2, 3]$$$.

По заданной последовательности размеров матрёшек $$$a_1, a_2, \dots, a_n$$$ определите минимальное количество наборов матрёшек, которые могут эту последовательность составлять.

Каждый набор используется полностью, то используются все его матрёшки. Каждый элемент заданной последовательности должен соответствовать ровно одной кукле из какого-то набора.

Входные данные

В первой строке входных данных дано единственное целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Далее следуют описания наборов входных данных.

Первая строка описания каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — суммарное количество матрёшек, которые были во всех наборах.

Вторая строка описания каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$)  — размеры матрёшек.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных теста не превосходит $$$2\cdot10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число $$$k$$$ — минимально возможное количество наборов, чтобы составить заданную последовательность.

Пример
Входные данные
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
Выходные данные
2
1
6
2
2
2
2
2
4
3
Примечание

Первый набор входных данных разобран в условии.

Во втором наборе входных данных все матрёшки могли быть частью одного набора с минимальным размером матрёшки $$$s=7$$$.

В третьем наборе входных данных каждая матрешка представляет собой отдельный набор.