Pequeña $\varepsilon$ y Pequeña $\omega$ son dos chicas amantes de la música. Para conmemorar un recuerdo que les pertenece solo a ellas dos, Pequeña $\varepsilon$ escribió una melodía para Pequeña $\omega$.

Pequeña $\varepsilon$ registró cada nota del movimiento como un número entero según su altura. Eligió una frase musical $a$ de longitud $k$ tal que $a$ es un desplazamiento cíclico de la secuencia $[1, 2, \dots, k]$; es decir, existe un entero no negativo $p$ ($0 \le p < k$) tal que $a = [p + 1, p + 2, \dots, k, 1, 2, \dots, p]$. A continuación, repitió esta frase una y otra vez y tomó las primeras $n$ notas para obtener la partitura original $b$.

Por ejemplo, cuando $k = 4$, $a$ puede ser una de $[1, 2, 3, 4]$, $[2, 3, 4, 1]$, $[3, 4, 1, 2]$ o $[4, 1, 2, 3]$. Si $a = [2, 3, 4, 1]$ y $n = 10$, entonces $b = [2, 3, 4, 1, 2, 3, 4, 1, 2, 3]$.

Antes de regalarle la melodía a Pequeña $\omega$, Pequeña $\varepsilon$ quiso añadirle su propio toque personal: puede realizar cualquier número de modificaciones y, en cada modificación, puede cambiar la nota en cualquier posición de la partitura por cualquier entero positivo. Tras varias modificaciones, la partitura original $b$ se convirtió en la partitura que Pequeña $\omega$ escuchó finalmente, $b'$.

Pequeña $\omega$ escuchó esta melodía $b'$ y supo el número $k$ por lo que Pequeña $\varepsilon$ murmuraba en sueños. Ahora Pequeña $\omega$ quiere saber cuántas notas como mínimo modificó Pequeña $\varepsilon$ para que la partitura original $b$ se convirtiera en la $b'$ que ella finalmente escuchó.

Entrada

La primera línea contiene un entero $T$ ($1 \le T \le 10^4$), que representa el número de casos de prueba.

Cada caso de prueba consta de dos líneas:

• La primera línea contiene dos enteros $n, k$ ($2 \le k \le n \le 2 \times 10^5$), que representan la longitud de la partitura y la longitud de la frase musical, respectivamente.
• La segunda línea contiene $n$ enteros $b'_1, b'_2, \dots, b'_n$ ($1 \le b'_i \le 10^9$), que representan las alturas de las notas que Pequeña $\omega$ escuchó finalmente.

Se garantiza que la suma de $n$ en todos los casos de prueba de un mismo archivo de prueba no supera $2 \times 10^5$.

Salida

Para cada caso de prueba, imprime una línea con un entero no negativo, que representa el número mínimo de notas modificadas por Pequeña $\varepsilon$.

Ejemplos

Entrada 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

Salida 1

0
1
2
4
2
2
6
2

Nota

Para el primer caso de prueba, se puede tomar $a = [2, 3, 1]$. En este caso, la partitura original es exactamente $b = [2, 3, 1, 2, 3, 1]$, que es idéntica a la partitura final, por lo que Pequeña $\varepsilon$ no modificó ninguna nota.

Para el segundo caso de prueba, se puede tomar $a = [1, 2, 3]$, obteniendo $b = [1, 2, 3, 1, 2]$. Basta con cambiar la última nota a $3$ para obtener la partitura final, por lo que la respuesta es $1$.

Para el tercer caso de prueba, se puede tomar $a = [4, 1, 2, 3]$, obteniendo $b = [4, 1, 2, 3, 4]$. Basta con cambiar la nota $2$-ésima a $3$ y la nota $4$-ésima a $1$ para obtener la partitura final, por lo que la respuesta es $2$.