Скоро Codeforces Round 1133 (Div. 1, Div. 2)! Регистрация здесь. ×

A. Выбор подмножеств
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Olivia Rodrigo - the cure

Вам даны массив $$$a$$$ из $$$n$$$ целых чисел и положительное целое число $$$k$$$.

Вы хотите распределить некоторые элементы массива $$$a$$$ по группам $$$S_1, S_2, \ldots, S_m$$$ ($$$m \ge 0$$$) так, чтобы:

  • каждая группа содержала хотя бы $$$k$$$ элементов;
  • каждый элемент массива $$$a$$$ входил не более чем в одну группу (элемент также может не входить ни в одну группу).

Найдите максимально возможное значение $$$\operatorname{mex}(\{\max(S_1), \max(S_2), \ldots, \max(S_m)\})$$$ среди всех допустимых способов сформировать группы, где $$$\operatorname{mex}(c)$$$ обозначает наименьшее неотрицательное целое число, которое не встречается в наборе $$$c$$$. Если $$$m = 0$$$, набор пуст и $$$\operatorname{mex}(\{\}) = 0$$$.

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

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

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

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

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

Для каждого набора входных данных выведите одно целое число — максимально возможное значение $$$\operatorname{mex}(\{\max(S_1), \max(S_2), \ldots, \max(S_m)\})$$$ среди всех допустимых способов сформировать группы.

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

В первом наборе входных данных один из оптимальных способов — сформировать группы $$$\{0\}$$$, $$$\{1\}$$$, $$$\{2\}$$$, что даёт $$$\operatorname{mex}(\{0, 1, 2\}) = 3$$$.

Во втором наборе входных данных один из оптимальных способов — сформировать единственную группу $$$\{1, 2, 3, 4\}$$$, что даёт $$$\operatorname{mex}(\{4\}) = 0$$$.

В третьем наборе входных данных один из оптимальных способов — сформировать группы $$$\{0, 0\}$$$ и $$$\{1, 1\}$$$, что даёт $$$\operatorname{mex}(\{0, 1\}) = 2$$$.