Read problem statements in [Russian], [Mandarin] and [Vietnamese] as well.

You are given a permutation P of integers from 1 to N, and an integer K such that $\lceil \frac{2N}{3}\rceil$ ≤ K ≤ N. In one operation, you can do the following:

Choose any consecutive segment of at most K elements of the permutation, and sort it in increasing order.

What's the smallest number of operations you have to make to sort the entire permutation in increasing order?

------ Input Format ------

• The first line of the input contains a single integer T - the number of test cases. The description of test cases follows.

• The first line of each test case contains two integers N, K.

• The second line of each test case contains $N integers P_{1}, P_{2}, \ldots, P_{N} -$ the elements of the permutation.

------ Output Format ------

For each test case, output the smallest number of operations you have to make to sort the entire permutation in increasing order.

------ Constraints ------

$1 ≤T ≤10^{4}$
$3 ≤N ≤2\cdot 10^{5}$
$\lceil \frac{2N}{3}\rceil ≤K ≤N$
$1 ≤P_{i} ≤N$
$P_{i} \neq P_{j}$ for $i\neq j$
- The sum of $N$ over all test cases doesn't exceed $10^{6}$.

----- Sample Input 1 ------
4
6 4
1 2 3 4 5 6
6 4
1 2 4 3 5 6
6 4
6 5 2 1 4 3
6 4
2 6 4 3 1 5

----- Sample Output 1 ------
0
1
2
3

----- explanation 1 ------
In the first test case, the permutation is already sorted.

In the second test case, you can choose segment $P[3:4]$ and sort it. The permutation will then be sorted.

In the third test case, you can sort segment $P[1:4]$ first, getting $(1, 2, 5, 6, 4, 3)$, and then $P[3:6]$.

In the fourth test case, you can sort segments in the order: $P[2:5]$, getting $(2, 1, 3, 4, 6, 5)$, then $P[1:2]$, getting $(1, 2, 3, 4, 6, 5)$, then $P[5:6]$, getting $(1, 2, 3, 4, 5, 6)$.

见题面

见题面