Lilla $\varepsilon$ och Lilla $\omega$ är två flickor som älskar musik. För att hedra ett minne som bara tillhör dem två skrev Lilla $\varepsilon$ en melodi till Lilla $\omega$.

Lilla $\varepsilon$ antecknade varje ton i satsen som ett heltal utifrån dess tonhöjd. Hon valde en musikalisk fras $a$ av längd $k$ sådan att $a$ är ett cykliskt skift av följden $[1, 2, \dots, k]$, det vill säga att det finns ett icke-negativt heltal $p$ ($0 \le p < k$) sådant att $a = [p + 1, p + 2, \dots, k, 1, 2, \dots, p]$. Därefter upprepade hon denna fras om och om igen och tog de första $n$ tonerna för att få det ursprungliga partituret $b$.

Till exempel, när $k = 4$, kan $a$ vara en av $[1, 2, 3, 4]$, $[2, 3, 4, 1]$, $[3, 4, 1, 2]$ eller $[4, 1, 2, 3]$. Om $a = [2, 3, 4, 1]$ och $n = 10$, så är $b = [2, 3, 4, 1, 2, 3, 4, 1, 2, 3]$.

Innan hon gav melodin till Lilla $\omega$ ville Lilla $\varepsilon$ sätta sin egen prägel på melodin: hon kunde utföra valfritt antal ändringar, och vid varje ändring kunde hon byta ut tonen på en valfri position i partituret mot ett valfritt positivt heltal. Efter ett antal ändringar blev det ursprungliga partituret $b$ det partitur som Lilla $\omega$ slutligen hörde, $b'$.

Lilla $\omega$ hörde denna melodi $b'$ och fick reda på talet $k$ genom att Lilla $\varepsilon$ pratade i sömnen. Nu vill Lilla $\omega$ veta det minsta antalet toner som Lilla $\varepsilon$ ändrade för att förvandla det ursprungliga partituret $b$ till det $b'$ som hon slutligen hörde.

Indata

Den första raden innehåller ett heltal $T$ ($1 \le T \le 10^4$), som anger antalet testfall.

Varje testfall består av två rader:

• Den första raden innehåller två heltal $n, k$ ($2 \le k \le n \le 2 \times 10^5$), som anger partiturets längd respektive frasens längd.
• Den andra raden innehåller $n$ heltal $b'_1, b'_2, \dots, b'_n$ ($1 \le b'_i \le 10^9$), som anger tonhöjderna för de toner som Lilla $\omega$ slutligen hörde.

Det garanteras att summan av $n$ över alla testfall i en enskild testfil inte överstiger $2 \times 10^5$.

Utdata

För varje testfall, skriv ut en rad med ett icke-negativt heltal som anger det minsta antalet toner som Lilla $\varepsilon$ har ändrat.

Exempel

Indata 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

Förklaring

För det första testfallet kan vi välja $a = [2, 3, 1]$. Då är det ursprungliga partituret precis $b = [2, 3, 1, 2, 3, 1]$, vilket är helt identiskt med det slutliga partituret, så Lilla $\varepsilon$ ändrade inga toner alls.

För det andra testfallet kan vi välja $a = [1, 2, 3]$, vilket ger $b = [1, 2, 3, 1, 2]$. Det räcker att ändra den sista tonen till $3$ för att få det slutliga partituret, så svaret är $1$.

För det tredje testfallet kan vi välja $a = [4, 1, 2, 3]$, vilket ger $b = [4, 1, 2, 3, 4]$. Det räcker att ändra den $2$:a tonen till $3$ och den $4$:e tonen till $1$ för att få det slutliga partituret, så svaret är $2$.