Маленька $\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$.