Litla $\varepsilon$ og Litla $\omega$ eru tvær stúlkur sem elska tónlist. Til að minnast minningar sem tilheyrir aðeins þeim tveimur samdi Litla $\varepsilon$ laglínu handa Litlu $\omega$.

Litla $\varepsilon$ skráði hverja nótu í kaflanum sem heiltölu eftir tónhæð hennar. Hún valdi tónhendingu $a$ af lengd $k$ þannig að $a$ er hringhliðrun á rununni $[1, 2, \dots, k]$, það er að segja að til er ekki-neikvæð heiltala $p$ ($0 \le p < k$) þannig að $a = [p + 1, p + 2, \dots, k, 1, 2, \dots, p]$. Síðan endurtók hún þessa tónhendingu aftur og aftur og tók fyrstu $n$ nóturnar til að fá upphaflega nótnablaðið $b$.

Til dæmis, þegar $k = 4$, getur $a$ verið ein af $[1, 2, 3, 4]$, $[2, 3, 4, 1]$, $[3, 4, 1, 2]$ eða $[4, 1, 2, 3]$. Ef $a = [2, 3, 4, 1]$ og $n = 10$, þá er $b = [2, 3, 4, 1, 2, 3, 4, 1, 2, 3]$.

Áður en hún færði Litlu $\omega$ laglínuna að gjöf vildi Litla $\varepsilon$ setja sinn eigin svip á laglínuna: hún gat gert hversu margar breytingar sem er, og í hverri breytingu gat hún breytt nótunni í hvaða einu sæti sem er á nótnablaðinu í hvaða jákvæðu heiltölu sem er. Eftir nokkrar breytingar varð upphaflega nótnablaðið $b$ að nótnablaðinu sem Litla $\omega$ heyrði að lokum, $b'$.

Litla $\omega$ heyrði þessa laglínu $b'$ og komst að tölunni $k$ þegar Litla $\varepsilon$ talaði upp úr svefni. Nú vill Litla $\omega$ vita hversu mörgum nótum Litla $\varepsilon$ breytti í það minnsta til að breyta upphaflega nótnablaðinu $b$ í $b'$ sem hún heyrði að lokum.

Inntak

Fyrsta línan inniheldur heiltölu $T$ ($1 \le T \le 10^4$), sem táknar fjölda prófunartilfella.

Hvert prófunartilfelli samanstendur af tveimur línum:

• Fyrri línan inniheldur tvær heiltölur $n, k$ ($2 \le k \le n \le 2 \times 10^5$), sem tákna lengd nótnablaðsins og lengd tónhendingarinnar.
• Seinni línan inniheldur $n$ heiltölur $b'_1, b'_2, \dots, b'_n$ ($1 \le b'_i \le 10^9$), sem tákna tónhæðir nótnanna sem Litla $\omega$ heyrði að lokum.

Tryggt er að summa $n$ yfir öll prófunartilfelli í einni prófunarskrá fari ekki yfir $2 \times 10^5$.

Úttak

Fyrir hvert prófunartilfelli skal prenta eina línu með ekki-neikvæðri heiltölu sem táknar lágmarksfjölda nótna sem Litla $\varepsilon$ breytti.

Dæmi

Inntak 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

Úttak 1

0
1
2
4
2
2
6
2

Skýring

Fyrir fyrsta prófunartilfellið má velja $a = [2, 3, 1]$. Þá er upphaflega nótnablaðið einmitt $b = [2, 3, 1, 2, 3, 1]$, sem er alveg eins og lokanótnablaðið, svo Litla $\varepsilon$ breytti engri nótu.

Fyrir annað prófunartilfellið má velja $a = [1, 2, 3]$, sem gefur $b = [1, 2, 3, 1, 2]$. Það nægir að breyta síðustu nótunni í $3$ til að fá lokanótnablaðið, svo svarið er $1$.

Fyrir þriðja prófunartilfellið má velja $a = [4, 1, 2, 3]$, sem gefur $b = [4, 1, 2, 3, 4]$. Það nægir að breyta nótu númer $2$ í $3$ og nótu númer $4$ í $1$ til að fá lokanótnablaðið, svo svarið er $2$.