Piccola $\varepsilon$ e Piccola $\omega$ sono due ragazze che amano la musica. Per commemorare un ricordo che appartiene solo a loro due, Piccola $\varepsilon$ ha scritto una melodia per Piccola $\omega$.

Piccola $\varepsilon$ ha annotato ogni nota del movimento come un numero intero in base alla sua altezza. Ha scelto una frase musicale $a$ di lunghezza $k$ tale che $a$ sia uno spostamento ciclico della sequenza $[1, 2, \dots, k]$, cioè esiste un intero non negativo $p$ ($0 \le p < k$) tale che $a = [p + 1, p + 2, \dots, k, 1, 2, \dots, p]$. Successivamente, ha ripetuto questa frase più e più volte e ha preso le prime $n$ note ottenendo lo spartito originale $b$.

Ad esempio, quando $k = 4$, $a$ può essere una tra $[1, 2, 3, 4]$, $[2, 3, 4, 1]$, $[3, 4, 1, 2]$ oppure $[4, 1, 2, 3]$. Se $a = [2, 3, 4, 1]$ e $n = 10$, allora $b = [2, 3, 4, 1, 2, 3, 4, 1, 2, 3]$.

Prima di regalare la melodia a Piccola $\omega$, Piccola $\varepsilon$ ha voluto aggiungere il proprio tocco personale alla melodia: può effettuare un numero qualsiasi di modifiche e, in ciascuna modifica, può cambiare la nota in una posizione qualsiasi dello spartito con un qualsiasi intero positivo. Dopo diverse modifiche, lo spartito originale $b$ è diventato lo spartito che Piccola $\omega$ ha infine ascoltato, $b'$.

Piccola $\omega$ ha ascoltato questa melodia $b'$ e ha scoperto il numero $k$ mentre Piccola $\varepsilon$ parlava nel sonno. Ora Piccola $\omega$ vuole sapere qual è il numero minimo di note che Piccola $\varepsilon$ ha modificato per trasformare lo spartito originale $b$ nello spartito $b'$ che lei ha infine ascoltato.

Input

La prima riga contiene un intero $T$ ($1 \le T \le 10^4$), che rappresenta il numero di casi di test.

Ogni caso di test è composto da due righe:

• La prima riga contiene due interi $n, k$ ($2 \le k \le n \le 2 \times 10^5$), che rappresentano rispettivamente la lunghezza dello spartito e la lunghezza della frase musicale.
• La seconda riga contiene $n$ interi $b'_1, b'_2, \dots, b'_n$ ($1 \le b'_i \le 10^9$), che rappresentano le altezze delle note che Piccola $\omega$ ha infine ascoltato.

È garantito che la somma di $n$ su tutti i casi di test in un singolo file di test non supera $2 \times 10^5$.

Output

Per ogni caso di test, stampa una riga contenente un intero non negativo, che rappresenta il numero minimo di note modificate da Piccola $\varepsilon$.

Esempi

Input 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

Output 1

0
1
2
4
2
2
6
2

Note

Per il primo caso di test, si può scegliere $a = [2, 3, 1]$. In questo caso lo spartito originale è esattamente $b = [2, 3, 1, 2, 3, 1]$, che è identico allo spartito finale, quindi Piccola $\varepsilon$ non ha modificato alcuna nota.

Per il secondo caso di test, si può scegliere $a = [1, 2, 3]$, ottenendo $b = [1, 2, 3, 1, 2]$. Basta cambiare l'ultima nota in $3$ per ottenere lo spartito finale, quindi la risposta è $1$.

Per il terzo caso di test, si può scegliere $a = [4, 1, 2, 3]$, ottenendo $b = [4, 1, 2, 3, 4]$. Basta cambiare la $2$-a nota in $3$ e la $4$-a nota in $1$ per ottenere lo spartito finale, quindi la risposta è $2$.