Tiểu $\varepsilon$ và Tiểu $\omega$ là hai cô gái yêu âm nhạc. Để kỷ niệm một ký ức chỉ thuộc về riêng hai người họ, Tiểu $\varepsilon$ đã viết một giai điệu dành tặng Tiểu $\omega$.

Tiểu $\varepsilon$ ghi lại mỗi nốt nhạc trong chương nhạc thành một số nguyên theo cao độ của nó. Cô chọn một câu nhạc $a$ có độ dài $k$ sao cho $a$ là một phép dịch vòng của dãy $[1, 2, \dots, k]$, tức là tồn tại số nguyên không âm $p$ ($0 \le p < k$) sao cho $a = [p + 1, p + 2, \dots, k, 1, 2, \dots, p]$. Tiếp theo, cô lặp đi lặp lại câu nhạc này nhiều lần và lấy $n$ nốt nhạc đầu tiên để thu được bản nhạc gốc $b$.

Ví dụ, khi $k = 4$, $a$ có thể là một trong các dãy $[1, 2, 3, 4]$, $[2, 3, 4, 1]$, $[3, 4, 1, 2]$ hoặc $[4, 1, 2, 3]$. Nếu $a = [2, 3, 4, 1]$ và $n = 10$, thì $b = [2, 3, 4, 1, 2, 3, 4, 1, 2, 3]$.

Trước khi tặng giai điệu cho Tiểu $\omega$, Tiểu $\varepsilon$ muốn tô điểm thêm sắc màu của riêng mình vào giai điệu: cô có thể thực hiện số lần chỉnh sửa tùy ý, trong mỗi lần chỉnh sửa, cô có thể đổi nốt nhạc ở một vị trí bất kỳ trong bản nhạc thành một số nguyên dương bất kỳ. Sau một số lần chỉnh sửa, bản nhạc gốc $b$ đã trở thành bản nhạc mà Tiểu $\omega$ nghe được cuối cùng là $b'$.

Tiểu $\omega$ đã nghe giai điệu $b'$ này và biết được con số $k$ qua lời nói mớ của Tiểu $\varepsilon$. Bây giờ Tiểu $\omega$ muốn biết Tiểu $\varepsilon$ đã chỉnh sửa ít nhất bao nhiêu nốt nhạc để biến bản nhạc gốc $b$ thành bản nhạc $b'$ mà cô nghe được cuối cùng.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $T$ ($1 \le T \le 10^4$), biểu thị số lượng bộ dữ liệu kiểm tra.

Mỗi bộ dữ liệu kiểm tra gồm hai dòng:

• Dòng đầu tiên chứa hai số nguyên $n, k$ ($2 \le k \le n \le 2 \times 10^5$), lần lượt biểu thị độ dài bản nhạc và độ dài câu nhạc.
• Dòng thứ hai chứa $n$ số nguyên $b'_1, b'_2, \dots, b'_n$ ($1 \le b'_i \le 10^9$), biểu thị cao độ của các nốt nhạc mà Tiểu $\omega$ nghe được cuối cùng.

Đảm bảo tổng của $n$ trong tất cả các bộ dữ liệu của một tệp kiểm tra không vượt quá $2 \times 10^5$.

Dữ liệu ra

Đối với mỗi bộ dữ liệu kiểm tra, in ra một dòng chứa một số nguyên không âm, biểu thị số lượng nốt nhạc ít nhất mà Tiểu $\varepsilon$ đã chỉnh sửa.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

0
1
2
4
2
2
6
2

Ghi chú

Đối với bộ dữ liệu thứ nhất, có thể chọn $a = [2, 3, 1]$. Khi đó bản nhạc gốc vừa đúng là $b = [2, 3, 1, 2, 3, 1]$, hoàn toàn giống với bản nhạc cuối cùng, do đó Tiểu $\varepsilon$ không chỉnh sửa bất kỳ nốt nhạc nào.

Đối với bộ dữ liệu thứ hai, có thể chọn $a = [1, 2, 3]$, thu được $b = [1, 2, 3, 1, 2]$. Chỉ cần đổi nốt nhạc cuối cùng thành $3$ là thu được bản nhạc cuối cùng, do đó đáp án là $1$.

Đối với bộ dữ liệu thứ ba, có thể chọn $a = [4, 1, 2, 3]$, thu được $b = [4, 1, 2, 3, 4]$. Chỉ cần đổi nốt nhạc thứ $2$ thành $3$ và nốt nhạc thứ $4$ thành $1$ là thu được bản nhạc cuối cùng, do đó đáp án là $2$.