Маленькая $\varepsilon$ и Маленькая $\omega$ — две девочки, которые очень любят музыку. Чтобы увековечить воспоминание, принадлежащее только им двоим, Маленькая $\varepsilon$ написала для Маленькой $\omega$ мелодию.

Маленькая $\varepsilon$ записала каждую ноту произведения в виде целого числа в соответствии с её высотой. Она выбрала некоторую музыкальную фразу $a$ длины $k$ так, что $a$ является некоторым циклическим сдвигом последовательности $[1, 2, \dots, k]$, то есть существует такое целое неотрицательное число $p$ ($0 \le p < k$), что $a = [p + 1, p + 2, \dots, k, 1, 2, \dots, p]$. Затем она повторила эту фразу много раз подряд и взяла первые $n$ нот, получив исходную партитуру $b$.

Например, при $k = 4$ фраза $a$ может быть одной из последовательностей $[1, 2, 3, 4]$, $[2, 3, 4, 1]$, $[3, 4, 1, 2]$ или $[4, 1, 2, 3]$. Если $a = [2, 3, 4, 1]$ и $n = 10$, то $b = [2, 3, 4, 1, 2, 3, 4, 1, 2, 3]$.

Прежде чем подарить мелодию Маленькой $\omega$, Маленькая $\varepsilon$ захотела добавить в неё собственные краски: она могла выполнить произвольное количество изменений, и при каждом изменении заменить ноту на любой одной позиции в партитуре на любое положительное целое число. После нескольких изменений исходная партитура $b$ превратилась в партитуру, которую в итоге услышала Маленькая $\omega$, — $b'$.

Маленькая $\omega$ услышала эту мелодию $b'$, а из бормотания Маленькой $\varepsilon$ во сне узнала число $k$. Теперь Маленькая $\omega$ хочет узнать, какое наименьшее количество нот изменила Маленькая $\varepsilon$, чтобы исходная партитура $b$ превратилась в услышанную ею в итоге партитуру $b'$.

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

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

Каждый набор входных данных состоит из двух строк:

• Первая строка содержит два целых числа $n, k$ ($2 \le k \le n \le 2 \times 10^5$) — длину партитуры и длину музыкальной фразы соответственно.
• Вторая строка содержит $n$ целых чисел $b'_1, b'_2, \dots, b'_n$ ($1 \le b'_i \le 10^9$), обозначающих высоту каждой ноты, которую в итоге услышала Маленькая $\omega$.

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

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

Для каждого набора входных данных выведите в отдельной строке одно целое неотрицательное число — наименьшее количество нот, которые изменила Маленькая $\varepsilon$.

Примеры

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

8
6 3
2 3 1 2 3 1
5 3
1 2 3 1 3
5 4
4 3 2 1 4
6 3
1 3 1 3 1 3
5 2
1 1 1 1 1
6 4
1 2 3 4 5 6
6 2
172 723 593 904 219 576
5 3
3 1 1000000000 999999999 1

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

0
1
2
4
2
2
6
2

Примечание

В первом наборе входных данных можно выбрать $a = [2, 3, 1]$. Тогда исходная партитура в точности равна $b = [2, 3, 1, 2, 3, 1]$ и полностью совпадает с итоговой партитурой, поэтому Маленькая $\varepsilon$ не изменила ни одной ноты.

Во втором наборе входных данных можно выбрать $a = [1, 2, 3]$, получив $b = [1, 2, 3, 1, 2]$. Достаточно изменить последнюю ноту на $3$, чтобы получить итоговую партитуру, поэтому ответ равен $1$.

В третьем наборе входных данных можно выбрать $a = [4, 1, 2, 3]$, получив $b = [4, 1, 2, 3, 4]$. Достаточно изменить $2$-ю ноту на $3$, а $4$-ю ноту на $1$, чтобы получить итоговую партитуру, поэтому ответ равен $2$.