Little $\varepsilon$ dan Little $\omega$ adalah dua gadis yang mencintai musik. Untuk mengenang sebuah kenangan yang hanya milik mereka berdua, Little $\varepsilon$ menuliskan sebuah melodi untuk Little $\omega$.

Little $\varepsilon$ mencatat setiap nada dalam gerakan musik tersebut sebagai sebuah bilangan bulat berdasarkan tinggi nadanya. Ia memilih suatu frasa musik $a$ dengan panjang $k$ sedemikian sehingga $a$ merupakan pergeseran siklik dari barisan $[1, 2, \dots, k]$, yaitu terdapat bilangan bulat tak negatif $p$ ($0 \le p < k$) sedemikian sehingga $a = [p + 1, p + 2, \dots, k, 1, 2, \dots, p]$. Selanjutnya, ia mengulangi frasa ini berulang kali dan mengambil $n$ nada pertama untuk mendapatkan partitur asli $b$.

Sebagai contoh, ketika $k = 4$, $a$ dapat berupa salah satu dari $[1, 2, 3, 4]$, $[2, 3, 4, 1]$, $[3, 4, 1, 2]$, atau $[4, 1, 2, 3]$. Jika $a = [2, 3, 4, 1]$ dan $n = 10$, maka $b = [2, 3, 4, 1, 2, 3, 4, 1, 2, 3]$.

Sebelum menghadiahkan melodi tersebut kepada Little $\omega$, Little $\varepsilon$ ingin menambahkan sentuhan warnanya sendiri pada melodi itu: ia dapat melakukan modifikasi sebanyak apa pun, dan pada setiap modifikasi, ia dapat mengubah nada pada satu posisi mana pun di dalam partitur menjadi bilangan bulat positif berapa pun. Setelah beberapa kali modifikasi, partitur asli $b$ berubah menjadi partitur yang akhirnya didengar oleh Little $\omega$, yaitu $b'$.

Little $\omega$ mendengar melodi $b'$ ini dan mengetahui bilangan $k$ dari igauan tidur Little $\varepsilon$. Sekarang Little $\omega$ ingin mengetahui berapa paling sedikit jumlah nada yang dimodifikasi oleh Little $\varepsilon$ untuk mengubah partitur asli $b$ menjadi $b'$ yang akhirnya ia dengar.

Masukan

Baris pertama berisi sebuah bilangan bulat $T$ ($1 \le T \le 10^4$), yang menyatakan banyaknya kasus uji.

Setiap kasus uji terdiri dari dua baris:

• Baris pertama berisi dua bilangan bulat $n, k$ ($2 \le k \le n \le 2 \times 10^5$), yang masing-masing menyatakan panjang partitur dan panjang frasa musik.
• Baris kedua berisi $n$ bilangan bulat $b'_1, b'_2, \dots, b'_n$ ($1 \le b'_i \le 10^9$), yang menyatakan tinggi nada dari masing-masing nada yang akhirnya didengar oleh Little $\omega$.

Dijamin bahwa jumlah $n$ di seluruh kasus uji dalam satu berkas uji tidak melebihi $2 \times 10^5$.

Keluaran

Untuk setiap kasus uji, keluarkan satu baris berisi sebuah bilangan bulat tak negatif, yang menyatakan jumlah nada minimum yang dimodifikasi oleh Little $\varepsilon$.

Contoh

Masukan 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

Keluaran 1

0
1
2
4
2
2
6
2

Catatan

Untuk kasus uji pertama, kita dapat memilih $a = [2, 3, 1]$. Pada keadaan ini partitur aslinya tepat $b = [2, 3, 1, 2, 3, 1]$, yang sama persis dengan partitur akhir, sehingga Little $\varepsilon$ tidak memodifikasi nada apa pun.

Untuk kasus uji kedua, kita dapat memilih $a = [1, 2, 3]$, sehingga diperoleh $b = [1, 2, 3, 1, 2]$. Cukup mengubah nada terakhir menjadi $3$ untuk mendapatkan partitur akhir, sehingga jawabannya adalah $1$.

Untuk kasus uji ketiga, kita dapat memilih $a = [4, 1, 2, 3]$, sehingga diperoleh $b = [4, 1, 2, 3, 4]$. Cukup mengubah nada ke-$2$ menjadi $3$ dan nada ke-$4$ menjadi $1$ untuk mendapatkan partitur akhir, sehingga jawabannya adalah $2$.