E. MEX против DIFF
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Тёти Люсине, как и у всех гениальных людей, имеются свои странности. Сегодня в качестве развлечения она решила посмотреть на противостояние двух могущественных функций. В зависимости от результата она решит, добавлять ли эти функции в CrowdScript.

Дан массив $$$a$$$ из $$$n$$$ неотрицательных целых чисел. За одну операцию вы можете заменить любое число в массиве на любое неотрицательное целое число.

Назовём стоимостью массива $$$\operatorname{DIFF}(a) - \operatorname{MEX}(a)$$$, где $$$\operatorname{MEX}$$$ множества чисел — это минимальное целое неотрицательное число, которого нет в множестве, а $$$\operatorname{DIFF}$$$ — количество различных чисел в массиве.

Например, $$$\operatorname{MEX}(\{1, 2, 3\}) = 0$$$, $$$\operatorname{MEX}(\{0, 1, 2, 4, 5\}) = 3$$$.

Вам необходимо определить, какую минимальную стоимость массива $$$a$$$ можно получить, если разрешено сделать не больше $$$k$$$ операций.

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

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

В первой строке описания каждого набора входных данных находится два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 10^5$$$, $$$0 \le k \le 10^5$$$) — размер массива $$$a$$$ и максимальное количество операций, которое можно сделать.

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

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

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

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

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

В первом наборе входных данных не требуется делать какие-либо операции, чтобы минимизировать $$$\operatorname{DIFF} - \operatorname{MEX}$$$.

Во втором наборе входных данных можно заменить $$$5$$$ на $$$1$$$. После этого массив $$$a$$$ будет $$$[0,\, 2,\, 4,\, 1]$$$, $$$\operatorname{DIFF} = 4$$$, $$$\operatorname{MEX} = \operatorname{MEX}(\{0, 1, 2, 4\}) = 3$$$, поэтому ответ равен $$$1$$$.

В третьем наборе входных данных один из возможных массивов $$$a$$$ будет $$$[4,\, 13,\, 0,\, 0,\, 13,\, 1,\, 2]$$$, $$$\operatorname{DIFF} = 5$$$, $$$\operatorname{MEX} = 3$$$.

В четвертом наборе входных данных один из возможных массивов $$$a$$$ будет $$$[1,\, 2,\, 3,\, 0,\, 0,\, 0]$$$.