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

Монокарп решил сыграть в новую игру. Для игры используется колода из $$$n$$$ карточек, причем на $$$i$$$-й карточке записано ровно одно целое число $$$a_i$$$.

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

Иными словами, если на предыдущем ходе Монокарп взял себе карточку, на которой записано число $$$x$$$, то на текущем ходе он может взять себе либо карточку, на которой записано число $$$x$$$, либо карточку, на которой записано число $$$x + 1$$$. Монокарп может взять любую карточку, которая удовлетворяет этим условиям, независимо от того, где именно она в колоде.

После того как Монокарп взял себе карточку на очередном ходе, она удаляется из колоды.

По правилам игры количество различных чисел, записанных на карточках, которые Монокарп забрал себе, не должно превышать $$$k$$$.

Если после очередного хода Монокарп не может взять карточку, не нарушая описанных правил, игра заканчивается.

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

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

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

Первая строка каждого набора содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le k \le n \le 200\,000$$$) — количество карточек в колоде и максимальное количество различных чисел, которые могут быть записаны на карточках, которые Монокарп забирает себе.

Во второй строке следует последовательность целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{9}$$$), где $$$a_i$$$ равно числу, которое записано на $$$i$$$-й карточке.

Дополнительное ограничение на входные данные: сумма $$$n$$$ по всем наборам входных данных не превосходит $$$200\,000$$$.

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

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

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

В первом примере Монокарпу нужно взять себе любую из карточек, на которых записано число $$$3$$$. В процессе двух следующих ходов ему нужно взять себе две оставшиеся в колоде карточки, на которых записано число $$$3$$$. В процессе трех следующих ходов ему нужно взять себе три карточки, на которых записано число $$$4$$$. После этого Монокарп не сможет взять ни одной карточки из колоды, при этом у него будет $$$6$$$ карточек.