На некоторой улице построены \(n\) домов, по порядку пронумерованных от \(1\) до \(n\). Дом номер \(i\) изначально покрашен в цвет \(c_i\). Улица называется красивой, если все дома на ней покрашены в один и тот же цвет. Маляр Том — ответственный за перекраску улицы так, чтобы она стала красивой. Скорость работы Тома определяется целым числом \(k\).
За один день Том может перекрасить некоторое количество домов, выполнив два следующих шага:
- Сначала он выбирает два целых числа \(l\) и \(r\) так, что \( 1 \le l \le r \le n \) и \( r - l + 1 = k \).
- Затем для всех домов \(i\) таких, что \(l \le i \le r\), он может либо перекрасить этот дом в любой цвет на свой выбор, либо пропустить и не перекрашивать этот дом.
Обратите внимание, что в один и тот же день Том может перекрашивать дома в разные цвета.
Том хочет знать минимальное количество дней, необходимое для того, чтобы сделать улицу красивой.
Выходные данные
Выведите \(t\) строк, каждая из которых содержит одно целое число: для каждого тестового случая минимальное количество дней, необходимое Тому, чтобы сделать улицу красивой.
Примечание
В первом тестовом случае Том может покрасить дома 1 и 2 в первый день в цвет 2, дома 5 и 6 во второй день в цвет 2, и последний дом в цвет 2 в третий день.
Во втором тестовом случае Том может, например, потратить 6 дней на покраску домов 1, 2, 4, 5, 6, 7 в цвет 3.
В третьем тестовом случае Том может покрасить первый дом в первый день, а дома 6, 7 и 8 во второй день в цвет 3.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|