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

Летом Вика любит бывать на даче. Там есть всё для отдыха: удобные качели, велосипеды и речка.

Через речку прокинут деревянный мостик, состоящий из $$$n$$$ дощечек. Он уже довольно старый и неказистый, поэтому Вика решила его покрасить. Да и в сарае как раз нашлись банки с краской $$$k$$$ цветов.

Покрасив каждую дощечку в один из $$$k$$$ цветов, Вика уже хотела пойти качаться на качелях, чтобы отдохнуть от работы. Однако поняла, что дом находится на другой стороне речки, а краска ещё не полностью засохла и ходить по мостику пока нельзя.

Чтобы не портить внешний вид мостика, Вика решила, что всё же пройдёт по нему, но наступая только на дощечки одного цвета. Так как иначе небольшой слой краски на её подошве испортит дощечку другого цвета. У девушки также осталось немного краски, но её хватит на перекрашивание лишь одной дощечки мостика.

Сейчас Вика стоит на земле перед первой дощечкой. Чтобы пройти по мостику, она выберет некоторые дощечки одинакового цвета (после перекрашивания), которые имеют номера $$$1 \le i_1 < i_2 < \ldots < i_m \le n$$$ (дощечки нумеруются с $$$1$$$ слева направо). Тогда Вике придётся переступить $$$i_1 - 1, i_2 - i_1 - 1, i_3 - i_2 - 1, \ldots, i_m - i_{m-1} - 1, n - i_m$$$ дощечек в результате каждого из $$$m + 1$$$ шагов.

Так как Вика боится упасть, она не хочет делать слишком длинные шаги. Помогите ей и скажите минимально возможное максимальное количество дощечек, через которые ей придётся переступить за один шаг, если в процессе перехода по мостику она может перекрасить одну (или ноль) дощечек в другой цвет.

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

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

В первой строке каждого набора входных данных содержатся два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$) — количество дощечек в мостике и количество различных цветов краски.

Во второй строке каждого набора входных данных содержится $$$n$$$ целых чисел $$$c_1, c_2, c_3, \dots, c_n$$$ ($$$1 \le c_i \le k$$$) — цвета, в которые Вика покрасила дощечки мостика.

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

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

Для каждого набора входных данных выведите единственное число — минимально возможное максимальное количество дощечек, через которое придётся переступить Вике за один шаг.

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

В первом наборе входных данных Вика может перекрасить дощечку посередине в цвет $$$1$$$ и пройти через мостик, не переступая через дощечки.

Во втором наборе входных данных Вика может перекрасить дощечку посередине в цвет $$$2$$$ и пройти через мостик, каждый раз переступая через одну дощечку.

В третьем наборе входных данных Вика может перекрасить предпоследнюю дощечку в цвет $$$2$$$ и пройти по мостику, наступая только на дощечки с номерами $$$2$$$ и $$$5$$$. Тогда Вике придётся переступить $$$1$$$, $$$2$$$ и $$$1$$$ дощечку при каждом шаге, поэтому ответ равен $$$2$$$.

В четвёртом наборе входных данных Вика может вовсе не перекрашивать мостик и пройти по нему, каждый раз переступая через две дощечки, идя по дощечкам цвета $$$3$$$.

В пятом наборе входных данных Вика может вовсе не перекрашивать мостик и пройти по нему, не переступая через дощечки.