B. Перекраска улицы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На некоторой улице построены $$$n$$$ домов, по порядку пронумерованных от $$$1$$$ до $$$n$$$. Дом номер $$$i$$$ изначально покрашен в цвет $$$c_i$$$. Улица называется красивой, если все дома на ней покрашены в один и тот же цвет. Маляр Том — ответственный за перекраску улицы так, чтобы она стала красивой. Скорость работы Тома определяется целым числом $$$k$$$.

За один день Том может перекрасить некоторое количество домов, выполнив два следующих шага:

  1. Сначала он выбирает два целых числа $$$l$$$ и $$$r$$$ так, что $$$ 1 \le l \le r \le n $$$ и $$$ r - l + 1 = k $$$.
  2. Затем для всех домов $$$i$$$ таких, что $$$l \le i \le r$$$, он может либо перекрасить этот дом в любой цвет на свой выбор, либо пропустить и не перекрашивать этот дом.

Обратите внимание, что в один и тот же день Том может перекрашивать дома в разные цвета.

Том хочет знать минимальное количество дней, необходимое для того, чтобы сделать улицу красивой.

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

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

Первая строка каждого тестового случая содержит одно целое число $$$n$$$ и $$$k$$$ ($$$1 \le k \le n \le 10^5$$$).

Вторая строка содержит $$$n$$$ целых чисел. $$$i$$$-е из этих чисел равно $$$c_i$$$ ($$$1 \le c_i \le 100$$$) — цвету, в который покрашен дом номе $$$i$$$ изначально.

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

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

Выведите $$$t$$$ строк, каждая из которых содержит одно целое число: для каждого тестового случая минимальное количество дней, необходимое Тому, чтобы сделать улицу красивой.

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

В первом тестовом случае Том может покрасить дома 1 и 2 в первый день в цвет 2, дома 5 и 6 во второй день в цвет 2, и последний дом в цвет 2 в третий день.

Во втором тестовом случае Том может, например, потратить 6 дней на покраску домов 1, 2, 4, 5, 6, 7 в цвет 3.

В третьем тестовом случае Том может покрасить первый дом в первый день, а дома 6, 7 и 8 во второй день в цвет 3.