Klein $\varepsilon$ und Klein $\omega$ sind zwei musikbegeisterte Mädchen. Um eine Erinnerung zu bewahren, die nur ihnen beiden gehört, schrieb Klein $\varepsilon$ für Klein $\omega$ eine Melodie.

Klein $\varepsilon$ notierte jede Note des Satzes entsprechend ihrer Tonhöhe als ganze Zahl. Sie wählte eine musikalische Phrase $a$ der Länge $k$, sodass $a$ eine zyklische Verschiebung der Folge $[1, 2, \dots, k]$ ist, d. h. es existiert eine nichtnegative ganze Zahl $p$ ($0 \le p < k$), sodass $a = [p + 1, p + 2, \dots, k, 1, 2, \dots, p]$ gilt. Anschließend wiederholte sie diese Phrase immer wieder und übernahm die ersten $n$ Noten, um die ursprüngliche Partitur $b$ zu erhalten.

Wenn beispielsweise $k = 4$ ist, kann $a$ eine der Folgen $[1, 2, 3, 4]$, $[2, 3, 4, 1]$, $[3, 4, 1, 2]$ oder $[4, 1, 2, 3]$ sein. Falls $a = [2, 3, 4, 1]$ und $n = 10$ ist, dann gilt $b = [2, 3, 4, 1, 2, 3, 4, 1, 2, 3]$.

Bevor sie die Melodie Klein $\omega$ schenkte, wollte Klein $\varepsilon$ der Melodie noch ihre eigene Note verleihen: Sie konnte beliebig viele Änderungen vornehmen, wobei sie bei jeder Änderung die Note an einer beliebigen Position in der Partitur in eine beliebige positive ganze Zahl abändern konnte. Nach einigen Änderungen wurde aus der ursprünglichen Partitur $b$ die Partitur, die Klein $\omega$ schließlich hörte, nämlich $b'$.

Klein $\omega$ hörte diese Melodie $b'$ und erfuhr aus dem Schlafreden von Klein $\varepsilon$ die Zahl $k$. Nun möchte Klein $\omega$ wissen, wie viele Noten Klein $\varepsilon$ mindestens geändert hat, um die ursprüngliche Partitur $b$ in die von ihr schließlich gehörte Partitur $b'$ zu verwandeln.

Eingabe

Die erste Zeile enthält eine ganze Zahl $T$ ($1 \le T \le 10^4$), die die Anzahl der Testfälle angibt.

Jeder Testfall besteht aus zwei Zeilen:

• Die erste Zeile enthält zwei ganze Zahlen $n, k$ ($2 \le k \le n \le 2 \times 10^5$), die die Länge der Partitur bzw. die Länge der Phrase angeben.
• Die zweite Zeile enthält $n$ ganze Zahlen $b'_1, b'_2, \dots, b'_n$ ($1 \le b'_i \le 10^9$), die die Tonhöhen der Noten angeben, die Klein $\omega$ schließlich gehört hat.

Es wird garantiert, dass die Summe von $n$ über alle Testfälle in einer einzelnen Testdatei $2 \times 10^5$ nicht überschreitet.

Ausgabe

Gib für jeden Testfall eine Zeile mit einer nichtnegativen ganzen Zahl aus, die die minimale Anzahl der von Klein $\varepsilon$ geänderten Noten angibt.

Beispiele

Eingabe 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

Ausgabe 1

0
1
2
4
2
2
6
2

Hinweis

Für den ersten Testfall kann man $a = [2, 3, 1]$ wählen. Dann lautet die ursprüngliche Partitur genau $b = [2, 3, 1, 2, 3, 1]$, was vollkommen mit der endgültigen Partitur übereinstimmt; daher hat Klein $\varepsilon$ keine einzige Note geändert.

Für den zweiten Testfall kann man $a = [1, 2, 3]$ wählen und erhält $b = [1, 2, 3, 1, 2]$. Man muss lediglich die letzte Note in $3$ ändern, um die endgültige Partitur zu erhalten, also ist die Antwort $1$.

Für den dritten Testfall kann man $a = [4, 1, 2, 3]$ wählen und erhält $b = [4, 1, 2, 3, 4]$. Man muss lediglich die $2$-te Note in $3$ und die $4$-te Note in $1$ ändern, um die endgültige Partitur zu erhalten, also ist die Antwort $2$.