Кішкентай $\varepsilon$ мен Кішкентай $\omega$ — музыканы жанындай жақсы көретін екі қыз. Тек екеуіне ғана тиесілі естелікті есте сақтау үшін Кішкентай $\varepsilon$ Кішкентай $\omega$-ға арнап бір әуен жазды.

Кішкентай $\varepsilon$ шығармадағы әрбір нотаны оның биіктігіне қарай бүтін сан ретінде жазып алды. Ол ұзындығы $k$ болатын қандай да бір $a$ музыкалық фразасын таңдап алды, мұндағы $a$ — $[1, 2, \dots, k]$ тізбегінің қандай да бір циклдік ығысуы, яғни $a = [p + 1, p + 2, \dots, k, 1, 2, \dots, p]$ болатындай теріс емес бүтін $p$ ($0 \le p < k$) саны табылады. Содан кейін ол осы музыкалық фразаны қайта-қайта қайталап, алғашқы $n$ нотаны қиып алу арқылы бастапқы $b$ партитурасын алды.

Мысалы, $k = 4$ болғанда, $a$ тізбегі $[1, 2, 3, 4]$, $[2, 3, 4, 1]$, $[3, 4, 1, 2]$ немесе $[4, 1, 2, 3]$ тізбектерінің бірі бола алады. Егер $a = [2, 3, 4, 1]$ және $n = 10$ болса, онда $b = [2, 3, 4, 1, 2, 3, 4, 1, 2, 3]$ болады.

Әуенді Кішкентай $\omega$-ға сыйламас бұрын, Кішкентай $\varepsilon$ әуенге өзіндік реңк қосқысы келді: ол кез келген рет өзгеріс енгізе алады және әр өзгерісте партитурадағы белгілі бір орында тұрған нотаны кез келген оң бүтін санға ауыстыра алады. Бірнеше өзгерістен кейін бастапқы $b$ партитурасы Кішкентай $\omega$ соңында естіген $b'$ партитурасына айналды.

Кішкентай $\omega$ осы $b'$ әуенін естіді және Кішкентай $\varepsilon$-ның ұйқысырап сөйлеген сөздерінен $k$ санын біліп алды. Енді Кішкентай $\omega$ бастапқы $b$ партитурасын өзі соңында естіген $b'$ партитурасына айналдыру үшін Кішкентай $\varepsilon$ кем дегенде қанша нотаны өзгерткенін білгісі келеді.

Кіріс деректер

Бірінші жолда тест жиындарының санын білдіретін бір бүтін сан $T$ ($1 \le T \le 10^4$) берілген.

Әрбір тест жиыны екі жолдан тұрады:

• Бірінші жолда сәйкесінше партитураның ұзындығы мен музыкалық фразаның ұзындығын білдіретін екі бүтін сан $n, k$ ($2 \le k \le n \le 2 \times 10^5$) берілген.
• Екінші жолда Кішкентай $\omega$ соңында естіген ноталардың биіктіктерін білдіретін $n$ бүтін сан $b'_1, b'_2, \dots, b'_n$ ($1 \le b'_i \le 10^9$) берілген.

Бір тест файлындағы барлық деректер бойынша $n$ сандарының қосындысы $2 \times 10^5$ мәнінен аспайтынына кепілдік беріледі.

Шығыс деректер

Әрбір тест жиыны үшін жеке жолға бір теріс емес бүтін санды — Кішкентай $\varepsilon$ өзгерткен ноталардың ең аз санын шығарыңыз.

Мысалдар

Кіріс деректер 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

Шығыс деректер 1

0
1
2
4
2
2
6
2

Түсініктеме

Бірінші тест жиыны үшін $a = [2, 3, 1]$ деп алуға болады. Бұл кезде бастапқы партитура дәл $b = [2, 3, 1, 2, 3, 1]$ болады да, соңғы партитурамен толықтай сәйкес келеді, сондықтан Кішкентай $\varepsilon$ ешқандай нотаны өзгертпеген.

Екінші тест жиыны үшін $a = [1, 2, 3]$ деп алып, $b = [1, 2, 3, 1, 2]$ партитурасын алуға болады. Соңғы партитураны алу үшін тек соңғы нотаны $3$ санына өзгерту жеткілікті, сондықтан жауабы — $1$.

Үшінші тест жиыны үшін $a = [4, 1, 2, 3]$ деп алып, $b = [4, 1, 2, 3, 4]$ партитурасын алуға болады. Соңғы партитураны алу үшін $2$-ші нотаны $3$ санына, ал $4$-ші нотаны $1$ санына өзгерту жеткілікті, сондықтан жауабы — $2$.