У вас есть \(n\) карт, на каждой карте написано число, а также фиксированное целое число \(k\). Вы можете выполнять следующую операцию любое количество раз:
- Выберите любые \(k\) карт, на которых написано одно и то же число.
- Обменяйте эти карты на \(k-1\) карт, каждая из которых может иметь любое число, которое вы выберете (включая число, написанное на меняемых вами картах).
Вот одна из возможных последовательностей операций для первого примера, в котором \(k=3\):
Какое минимальное количество карт у вас может остаться в конце этого процесса?
Выходные данные
Для каждого теста выведите одно целое число — минимальное количество карт, которые у вас могут остаться после любого количества операций.
Примечание
Первый пример соответствует изображению выше. Последовательность операций, отображенная там, является оптимальной, поэтому ответ равен \(2\).
Во втором примере операции выполнить нельзя, поэтому ответ равен \(1\).
В четвертом примере вы можете многократно выбирать \(4\) карты с номером \(1\) и заменять их на \(3\) карты с номером \(1\), пока не останется \(3\) карты.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|