Petite $\varepsilon$ et Petite $\omega$ sont deux filles passionnées de musique. Pour commémorer un souvenir qui n'appartient qu'à elles deux, Petite $\varepsilon$ a composé une mélodie pour Petite $\omega$.

Petite $\varepsilon$ a noté chaque note du mouvement sous la forme d'un entier selon sa hauteur. Elle a choisi une phrase musicale $a$ de longueur $k$ telle que $a$ soit un décalage circulaire de la séquence $[1, 2, \dots, k]$, c'est-à-dire qu'il existe un entier naturel $p$ ($0 \le p < k$) tel que $a = [p + 1, p + 2, \dots, k, 1, 2, \dots, p]$. Ensuite, elle a répété cette phrase musicale encore et encore, et a conservé les $n$ premières notes pour obtenir la partition originale $b$.

Par exemple, lorsque $k = 4$, $a$ peut être l'une des séquences $[1, 2, 3, 4]$, $[2, 3, 4, 1]$, $[3, 4, 1, 2]$ ou $[4, 1, 2, 3]$. Si $a = [2, 3, 4, 1]$ et $n = 10$, alors $b = [2, 3, 4, 1, 2, 3, 4, 1, 2, 3]$.

Avant d'offrir la mélodie à Petite $\omega$, Petite $\varepsilon$ a voulu y ajouter sa propre touche : elle peut effectuer un nombre quelconque de modifications, et lors de chaque modification, elle peut remplacer la note située à n'importe quelle position de la partition par n'importe quel entier strictement positif. Après plusieurs modifications, la partition originale $b$ est devenue la partition finalement entendue par Petite $\omega$, notée $b'$.

Petite $\omega$ a entendu cette mélodie $b'$ et a appris le nombre $k$ en écoutant Petite $\varepsilon$ parler dans son sommeil. Maintenant, Petite $\omega$ aimerait savoir combien de notes au minimum Petite $\varepsilon$ a modifiées pour transformer la partition originale $b$ en la partition $b'$ qu'elle a finalement entendue.

Entrée

La première ligne contient un entier $T$ ($1 \le T \le 10^4$), représentant le nombre de cas de test.

Chaque cas de test comprend deux lignes :

• La première ligne contient deux entiers $n, k$ ($2 \le k \le n \le 2 \times 10^5$), représentant respectivement la longueur de la partition et la longueur de la phrase musicale.
• La deuxième ligne contient $n$ entiers $b'_1, b'_2, \dots, b'_n$ ($1 \le b'_i \le 10^9$), représentant les hauteurs des notes finalement entendues par Petite $\omega$.

Il est garanti que la somme de $n$ sur l'ensemble des cas de test d'un même fichier de test ne dépasse pas $2 \times 10^5$.

Sortie

Pour chaque cas de test, affichez sur une seule ligne un entier naturel représentant le nombre minimal de notes modifiées par Petite $\varepsilon$.

Exemples

Entrée 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

Sortie 1

0
1
2
4
2
2
6
2

Remarque

Pour le premier cas de test, on peut choisir $a = [2, 3, 1]$. La partition originale est alors exactement $b = [2, 3, 1, 2, 3, 1]$, ce qui est identique à la partition finale ; Petite $\varepsilon$ n'a donc modifié aucune note.

Pour le deuxième cas de test, on peut choisir $a = [1, 2, 3]$, ce qui donne $b = [1, 2, 3, 1, 2]$. Il suffit de remplacer la dernière note par $3$ pour obtenir la partition finale ; la réponse est donc $1$.

Pour le troisième cas de test, on peut choisir $a = [4, 1, 2, 3]$, ce qui donne $b = [4, 1, 2, 3, 4]$. Il suffit de remplacer la $2$-ième note par $3$ et la $4$-ième note par $1$ pour obtenir la partition finale ; la réponse est donc $2$.