C. Нужно больше массивов
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив $$$a$$$ и $$$n$$$ целых чисел. Он отсортирован в порядке неубывания, то есть $$$a_i \le a_{i + 1}$$$ для всех $$$1 \le i \lt n$$$.

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

  • $$$a_1$$$ выписывается в новый массив;
  • если $$$a_1 + 1 \lt a_2$$$, то $$$a_2$$$ выписывается в новый массив, иначе $$$a_2$$$ выписывается в тот же массив, что и $$$a_1$$$;
  • если $$$a_2 + 1 \lt a_3$$$, то $$$a_3$$$ выписывается в новый массив, иначе $$$a_3$$$ выписывается в тот же массив, что и $$$a_2$$$;
  • $$$\cdots$$$

Например, если $$$a=[1, 2, 4, 6]$$$, то:

  • $$$a_1 = 1$$$ выписывается в новый массив, полученные массивы: $$$[1]$$$
  • $$$a_1 + 1 = 2$$$, поэтому $$$a_2 = 2$$$ дописывается в уже существующий массив, полученные массивы: $$$[1, 2]$$$;
  • $$$a_2 + 1 = 3$$$, поэтому $$$a_3 = 4$$$ выписывается в новый массив, полученные массивы: $$$[1, 2]$$$ и $$$[4]$$$;
  • $$$a_3 + 1 = 5$$$, поэтому $$$a_4 = 6$$$ выписывается в новый массив, полученные массивы: $$$[1, 2]$$$, $$$[4]$$$ и $$$[6]$$$.

Ваша задача — удалить элементы так, чтобы в результате описанного выше алгоритма создалось как можно больше массивов. Если вы удалите все элементы из массива, то не будет создано ни одного нового массива.

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

Первая строка входных данных содержит одно целое число $$$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^6$$$, $$$a_i \le a_{i + 1}$$$) — элементы массива.

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

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

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

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

В первом примере можно удалить $$$a_3$$$ и $$$a_5$$$, тогда $$$a=[1, 2, 4, 6]$$$, процесс составления массивов для него показан в условии.

Во втором примере нужно удалить $$$a_2$$$, после этого $$$a = [1, 3]$$$, а выписаны будут массивы $$$[1]$$$ и $$$[3]$$$.

В третьем примере удаления делать не нужно, для $$$a = [1, 2, 2, 4]$$$ выписаны будут массивы $$$[1, 2, 2]$$$ и $$$[4]$$$.