Pikku $\varepsilon$ ja Pikku $\omega$ ovat kaksi musiikkia rakastavaa tyttöä. Juhlistaakseen muistoa, joka kuuluu vain heille kahdelle, Pikku $\varepsilon$ kirjoitti Pikku $\omega$:lle melodian.

Pikku $\varepsilon$ merkitsi osan jokaisen sävelen kokonaisluvuksi sen sävelkorkeuden mukaan. Hän valitsi jonkin pituisen $k$ musiikillisen fraasin $a$ siten, että $a$ on jonon $[1, 2, \dots, k]$ jokin syklinen siirros, eli on olemassa epänegatiivinen kokonaisluku $p$ ($0 \le p < k$), jolle $a = [p + 1, p + 2, \dots, k, 1, 2, \dots, p]$. Tämän jälkeen hän toisti tätä fraasia yhä uudelleen ja otti ensimmäiset $n$ säveltä saadakseen alkuperäisen nuotin $b$.

Esimerkiksi kun $k = 4$, $a$ voi olla yksi jonoista $[1, 2, 3, 4]$, $[2, 3, 4, 1]$, $[3, 4, 1, 2]$ tai $[4, 1, 2, 3]$. Jos $a = [2, 3, 4, 1]$ ja $n = 10$, niin $b = [2, 3, 4, 1, 2, 3, 4, 1, 2, 3]$.

Ennen kuin Pikku $\omega$ sai melodian lahjaksi, Pikku $\varepsilon$ halusi lisätä melodiaan oman sävynsä: hän voi tehdä mielivaltaisen määrän muutoksia, ja jokaisessa muutoksessa hän voi muuttaa nuotin missä tahansa yksittäisessä kohdassa olevan sävelen miksi tahansa positiiviseksi kokonaisluvuksi. Useiden muutosten jälkeen alkuperäisestä nuotista $b$ tuli Pikku $\omega$:n lopulta kuulema nuotti $b'$.

Pikku $\omega$ kuuli tämän melodian $b'$ ja sai tietää luvun $k$ Pikku $\varepsilon$:n unissapuhumisesta. Nyt Pikku $\omega$ haluaa tietää, kuinka monta säveltä Pikku $\varepsilon$ vähintään muutti, jotta alkuperäinen nuotti $b$ muuttui hänen lopulta kuulemakseen nuotiksi $b'$.

Syöte

Ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T \le 10^4$), joka ilmoittaa testitapausten lukumäärän.

Jokainen testitapaus koostuu kahdesta rivistä:

• Ensimmäinen rivi sisältää kaksi kokonaislukua $n, k$ ($2 \le k \le n \le 2 \times 10^5$), jotka ilmoittavat nuotin pituuden ja fraasin pituuden.
• Toinen rivi sisältää $n$ kokonaislukua $b'_1, b'_2, \dots, b'_n$ ($1 \le b'_i \le 10^9$), jotka ilmoittavat Pikku $\omega$:n lopulta kuulemien sävelten sävelkorkeudet.

On taattu, että lukujen $n$ summa kaikissa yhden testitiedoston testitapauksissa on enintään $2 \times 10^5$.

Tuloste

Tulosta jokaista testitapausta kohden yhdelle riville epänegatiivinen kokonaisluku, joka ilmoittaa Pikku $\varepsilon$:n muuttamien sävelten vähimmäismäärän.

Esimerkit

Syöte 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

Tuloste 1

0
1
2
4
2
2
6
2

Huomautus

Ensimmäisessä testitapauksessa voidaan valita $a = [2, 3, 1]$. Tällöin alkuperäinen nuotti on täsmälleen $b = [2, 3, 1, 2, 3, 1]$, joka on täysin sama kuin lopullinen nuotti, joten Pikku $\varepsilon$ ei muuttanut yhtäkään säveltä.

Toisessa testitapauksessa voidaan valita $a = [1, 2, 3]$, jolloin saadaan $b = [1, 2, 3, 1, 2]$. Riittää muuttaa viimeinen sävel luvuksi $3$, jotta saadaan lopullinen nuotti, joten vastaus on $1$.

Kolmannessa testitapauksessa voidaan valita $a = [4, 1, 2, 3]$, jolloin saadaan $b = [4, 1, 2, 3, 4]$. Riittää muuttaa $2$. sävel luvuksi $3$ ja $4$. sävel luvuksi $1$, jotta saadaan lopullinen nuotti, joten vastaus on $2$.