Lille $\varepsilon$ og Lille $\omega$ er to jenter som elsker musikk. For å minnes et minne som bare tilhører dem to, skrev Lille $\varepsilon$ en melodi til Lille $\omega$.

Lille $\varepsilon$ noterte hver tone i satsen som et heltall etter tonehøyden. Hun valgte en musikalsk frase $a$ med lengde $k$ slik at $a$ er et syklisk skift av følgen $[1, 2, \dots, k]$, det vil si at det finnes et ikke-negativt heltall $p$ ($0 \le p < k$) slik at $a = [p + 1, p + 2, \dots, k, 1, 2, \dots, p]$. Deretter gjentok hun denne frasen om og om igjen, og tok de første $n$ tonene for å få det opprinnelige partituret $b$.

For eksempel, når $k = 4$, kan $a$ være én av $[1, 2, 3, 4]$, $[2, 3, 4, 1]$, $[3, 4, 1, 2]$ eller $[4, 1, 2, 3]$. Hvis $a = [2, 3, 4, 1]$ og $n = 10$, så er $b = [2, 3, 4, 1, 2, 3, 4, 1, 2, 3]$.

Før hun ga melodien til Lille $\omega$, ville Lille $\varepsilon$ sette sitt eget preg på melodien: hun kunne gjøre så mange endringer hun ville, og i hver endring kunne hun bytte ut tonen på én valgfri posisjon i partituret med et hvilket som helst positivt heltall. Etter noen endringer ble det opprinnelige partituret $b$ til partituret som Lille $\omega$ til slutt hørte, $b'$.

Lille $\omega$ hørte denne melodien $b'$, og fikk vite tallet $k$ da Lille $\varepsilon$ snakket i søvne. Nå vil Lille $\omega$ vite hvor få toner Lille $\varepsilon$ minst måtte endre for at det opprinnelige partituret $b$ skulle bli til det $b'$ som hun til slutt hørte.

Inndata

Den første linjen inneholder et heltall $T$ ($1 \le T \le 10^4$), som angir antall testtilfeller.

Hvert testtilfelle består av to linjer:

• Den første linjen inneholder to heltall $n, k$ ($2 \le k \le n \le 2 \times 10^5$), som angir henholdsvis lengden på partituret og lengden på frasen.
• Den andre linjen inneholder $n$ heltall $b'_1, b'_2, \dots, b'_n$ ($1 \le b'_i \le 10^9$), som angir tonehøydene til tonene som Lille $\omega$ til slutt hørte.

Det garanteres at summen av $n$ over alle testtilfeller i én enkelt testfil ikke overstiger $2 \times 10^5$.

Utdata

For hvert testtilfelle skal du skrive ut én linje med et ikke-negativt heltall som angir det minste antallet toner Lille $\varepsilon$ har endret.

Eksempler

Inndata 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

Utdata 1

0
1
2
4
2
2
6
2

Forklaring

For det første testtilfellet kan vi velge $a = [2, 3, 1]$. Da er det opprinnelige partituret nøyaktig $b = [2, 3, 1, 2, 3, 1]$, som er helt likt det endelige partituret, så Lille $\varepsilon$ endret ingen toner.

For det andre testtilfellet kan vi velge $a = [1, 2, 3]$, og få $b = [1, 2, 3, 1, 2]$. Vi trenger bare å endre den siste tonen til $3$ for å få det endelige partituret, så svaret er $1$.

For det tredje testtilfellet kan vi velge $a = [4, 1, 2, 3]$, og få $b = [4, 1, 2, 3, 4]$. Vi trenger bare å endre den $2$. tonen til $3$ og den $4$. tonen til $1$ for å få det endelige partituret, så svaret er $2$.