Bạn được cho một hoán vị \(p\) có độ dài \(n\) và một số nguyên dương \(k \leq n\).

Trong một thao tác, bạn:

• Chọn \(k\) phần tử riêng biệt \(p_{i_1}, p_{i_2}, \ldots, p_{i_k}\).
• Loại bỏ chúng và sau đó thêm chúng đã được sắp xếp theo thứ tự tăng dần vào cuối hoán vị.

Ví dụ, nếu \(p = [2,5,1,3,4]\) và \(k = 2\) và bạn chọn các phần tử \(5\) và \(3\) cho thao tác, thì \([2, 5, 1, 3, 4] \rightarrow [2, 1, 4, 3, 5]\).

Tìm số thao tác tối thiểu cần thiết để sắp xếp hoán vị theo thứ tự tăng dần. Có thể chứng minh rằng luôn có thể làm như vậy.

Input

• Dòng đầu tiên chứa một số nguyên \(t\) \((1 \leq t \leq 10^4)\) — số lượng bộ kiểm tra. Mô tả của các bộ kiểm tra theo sau.
• Dòng đầu tiên của mỗi bộ kiểm tra chứa hai số nguyên \(n\) và \(k\) \((2 \leq n \leq 10^5, 1 \leq k \leq n)\).
• Dòng thứ hai của mỗi bộ kiểm tra chứa \(n\) số nguyên \(p_1, p_2, \ldots, p_n\). \((1 \leq p_i \leq n)\). Được đảm bảo rằng \(p\) là một hoán vị.

Output

• Đối với mỗi bộ kiểm tra, xuất ra một số nguyên — số thao tác tối thiểu cần thiết để sắp xếp hoán vị.

Example

4
3 2
1 2 3
3 1
3 1 2
4 2
1 3 2 4
4 2
2 3 1 4

0
1
1
2