Mała $\varepsilon$ i Mała $\omega$ to dwie dziewczyny, które kochają muzykę. Aby upamiętnić wspomnienie należące tylko do nich dwóch, Mała $\varepsilon$ napisała melodię dla Małej $\omega$.

Mała $\varepsilon$ zapisała każdą nutę w części utworu jako liczbę całkowitą odpowiadającą jej wysokości. Wybrała pewną frazę muzyczną $a$ o długości $k$ taką, że $a$ jest pewnym przesunięciem cyklicznym ciągu $[1, 2, \dots, k]$, to znaczy istnieje nieujemna liczba całkowita $p$ ($0 \le p < k$) taka, że $a = [p + 1, p + 2, \dots, k, 1, 2, \dots, p]$. Następnie powtórzyła tę frazę wielokrotnie i wzięła pierwsze $n$ nut, otrzymując oryginalny zapis nutowy $b$.

Na przykład, gdy $k = 4$, $a$ może być jednym z ciągów $[1, 2, 3, 4]$, $[2, 3, 4, 1]$, $[3, 4, 1, 2]$ lub $[4, 1, 2, 3]$. Jeśli $a = [2, 3, 4, 1]$ oraz $n = 10$, to $b = [2, 3, 4, 1, 2, 3, 4, 1, 2, 3]$.

Zanim podarowała melodię Małej $\omega$, Mała $\varepsilon$ chciała dodać do niej swój własny akcent: mogła wykonać dowolną liczbę modyfikacji, a w każdej modyfikacji mogła zmienić nutę na jednej wybranej pozycji w zapisie nutowym na dowolną dodatnią liczbę całkowitą. Po pewnych modyfikacjach oryginalny zapis nutowy $b$ zamienił się w zapis nutowy, który ostatecznie usłyszała Mała $\omega$, czyli $b'$.

Mała $\omega$ usłyszała tę melodię $b'$ i poznała liczbę $k$ z sennych mamrotań Małej $\varepsilon$. Teraz Mała $\omega$ chciałaby się dowiedzieć, ile co najmniej nut zmodyfikowała Mała $\varepsilon$, aby oryginalny zapis nutowy $b$ stał się ostatecznie usłyszanym przez nią zapisem $b'$.

Wejście

Pierwszy wiersz zawiera jedną liczbę całkowitą $T$ ($1 \le T \le 10^4$), oznaczającą liczbę zestawów danych testowych.

Każdy zestaw danych testowych składa się z dwóch wierszy:

• Pierwszy wiersz zawiera dwie liczby całkowite $n, k$ ($2 \le k \le n \le 2 \times 10^5$), oznaczające odpowiednio długość zapisu nutowego oraz długość frazy muzycznej.
• Drugi wiersz zawiera $n$ liczb całkowitych $b'_1, b'_2, \dots, b'_n$ ($1 \le b'_i \le 10^9$), oznaczających wysokości poszczególnych nut, które ostatecznie usłyszała Mała $\omega$.

Gwarantuje się, że suma wartości $n$ po wszystkich zestawach danych w pojedynczym pliku testowym nie przekracza $2 \times 10^5$.

Wyjście

Dla każdego zestawu danych testowych wypisz w osobnym wierszu jedną nieujemną liczbę całkowitą, oznaczającą minimalną liczbę nut zmodyfikowanych przez Małą $\varepsilon$.

Przykład

Wejście 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

Wyjście 1

0
1
2
4
2
2
6
2

Uwagi

Dla pierwszego zestawu danych można przyjąć $a = [2, 3, 1]$. Wówczas oryginalny zapis nutowy to dokładnie $b = [2, 3, 1, 2, 3, 1]$, który jest identyczny z końcowym zapisem nutowym, zatem Mała $\varepsilon$ nie zmodyfikowała żadnej nuty.

Dla drugiego zestawu danych można przyjąć $a = [1, 2, 3]$, otrzymując $b = [1, 2, 3, 1, 2]$. Wystarczy zmienić ostatnią nutę na $3$, aby otrzymać końcowy zapis nutowy, więc odpowiedzią jest $1$.

Dla trzeciego zestawu danych można przyjąć $a = [4, 1, 2, 3]$, otrzymując $b = [4, 1, 2, 3, 4]$. Wystarczy zmienić $2$-gą nutę na $3$ oraz $4$-tą nutę na $1$, aby otrzymać końcowy zapis nutowy, więc odpowiedzią jest $2$.