Little $\varepsilon$ and Little $\omega$ are two girls who love music. To commemorate a memory that belongs only to the two of them, Little $\varepsilon$ wrote a melody for Little $\omega$.

Little $\varepsilon$ recorded each note in the movement as an integer according to its pitch. She chose a musical phrase $a$ of length $k$ such that $a$ is a cyclic shift of the sequence $[1, 2, \dots, k]$; that is, there exists a non-negative integer $p$ ($0 \le p < k$) such that $a = [p + 1, p + 2, \dots, k, 1, 2, \dots, p]$. Then, she repeated this phrase over and over again and took the first $n$ notes to obtain the original score $b$.

For example, when $k = 4$, $a$ can be one of $[1, 2, 3, 4]$, $[2, 3, 4, 1]$, $[3, 4, 1, 2]$, or $[4, 1, 2, 3]$. If $a = [2, 3, 4, 1]$ and $n = 10$, then $b = [2, 3, 4, 1, 2, 3, 4, 1, 2, 3]$.

Before gifting the melody to Little $\omega$, Little $\varepsilon$ wanted to add her own touch to the melody: she could perform any number of modifications, and in each modification, she could change the note at any single position in the score to any positive integer. After several modifications, the original score $b$ became the score that Little $\omega$ finally heard, $b'$.

Little $\omega$ heard this melody $b'$ and learned the number $k$ from Little $\varepsilon$'s sleep talk. Now Little $\omega$ wants to know the minimum number of notes Little $\varepsilon$ modified to turn the original score $b$ into the $b'$ that she finally heard.

Input

The first line contains an integer $T$ ($1 \le T \le 10^4$), representing the number of test cases.

Each test case consists of two lines:

• The first line contains two integers $n, k$ ($2 \le k \le n \le 2 \times 10^5$), representing the length of the score and the length of the phrase, respectively.
• The second line contains $n$ integers $b'_1, b'_2, \dots, b'_n$ ($1 \le b'_i \le 10^9$), representing the pitches of the notes that Little $\omega$ finally heard.

It is guaranteed that the sum of $n$ over all test cases in a single test file does not exceed $2 \times 10^5$.

Output

For each test case, output a single line containing a non-negative integer, representing the minimum number of notes modified by Little $\varepsilon$.

Examples

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

For the first test case, we can choose $a = [2, 3, 1]$. Then the original score is $b = [2, 3, 1, 2, 3, 1]$, which is identical to the final score, so Little $\varepsilon$ did not modify any notes.

For the second test case, we can choose $a = [1, 2, 3]$, obtaining $b = [1, 2, 3, 1, 2]$. Changing only the last note to $3$ yields the final score, so the answer is $1$.

For the third test case, we can choose $a = [4, 1, 2, 3]$, obtaining $b = [4, 1, 2, 3, 4]$. Changing the $2$-nd note to $3$ and the $4$-th note to $1$ yields the final score, so the answer is $2$.