A. Обмен картами
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть $$$n$$$ карт, на каждой карте написано число, а также фиксированное целое число $$$k$$$. Вы можете выполнять следующую операцию любое количество раз:

  • Выберите любые $$$k$$$ карт, на которых написано одно и то же число.
  • Обменяйте эти карты на $$$k-1$$$ карт, каждая из которых может иметь любое число, которое вы выберете (включая число, написанное на меняемых вами картах).

Вот одна из возможных последовательностей операций для первого примера, в котором $$$k=3$$$:

Какое минимальное количество карт у вас может остаться в конце этого процесса?

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

Первая строка ввода содержит одно целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество тестов. Затем следует описание тестов.

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

Следующая строка каждого теста содержит $$$n$$$ целых чисел $$$c_1, c_2, \ldots c_n$$$ ($$$1 \le c_i \le 100$$$) — числа, написанные на ваших картах.

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

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

Пример
Входные данные
7
5 3
4 1 1 4 4
1 10
7
7 2
4 2 1 100 5 2 3
10 4
1 1 1 1 1 1 1 1 1 1
5 2
3 8 1 48 7
6 2
10 20 30 10 20 40
6 3
10 20 30 10 20 40
Выходные данные
2
1
1
3
5
1
6
Примечание

Первый пример соответствует изображению выше. Последовательность операций, отображенная там, является оптимальной, поэтому ответ равен $$$2$$$.

Во втором примере операции выполнить нельзя, поэтому ответ равен $$$1$$$.

В четвертом примере вы можете многократно выбирать $$$4$$$ карты с номером $$$1$$$ и заменять их на $$$3$$$ карты с номером $$$1$$$, пока не останется $$$3$$$ карты.