B. Поход в кинотеатр
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В компании из $$$n$$$ человек организуется поход в кинотеатр. Каждый человек может либо пойти, либо нет. Это зависит от того, сколько ещё народу пойдёт. А именно, каждый человек $$$i$$$ сказал: «Я хочу пойти в кинотеатр тогда и только тогда, когда пойдут хотя бы ещё $$$a_i$$$ других человек, не считая меня». Это значит, что $$$i$$$-й человек расстроится в двух случаях:

  • если он пойдёт в кинотеатр, а кроме него пойдут строго менее $$$a_i$$$ других человек; или
  • если он не пойдёт в кинотеатр, но при этом пойдут хотя бы $$$a_i$$$ других человек.

Сколько есть способов выбрать множество людей, идущих в кинотеатр, чтобы никто не расстроился?

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

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

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

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le n - 1$$$) — числа из высказываний людей.

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

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

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

Пример
Входные данные
4
2
1 1
7
0 1 2 3 4 5 6
8
6 0 3 3 6 7 2 7
5
3 0 0 3 3
Выходные данные
2
1
3
2
Примечание

В первом наборе входных данных оба человека хотят пойти тогда и только тогда, когда другой человек пойдёт. Есть два подходящих варианта: либо оба пойдут, либо оба не пойдут. Если же пойдёт лишь один из двоих, то оба окажутся расстроены.

Во втором наборе входных данных в кинотеатр должны пойти все. В любом другом варианте обязательно кто-нибудь расстроится.

В третьем наборе входных данных есть три допустимых варианта: либо идёт человек с номером $$$2$$$; либо идут люди с номерами $$$2, 3, 4, 7$$$; либо идут все восемь человек.