Sorting Array (Large)

We are building a somewhat unusual algorithm that sorts an array $A$ containing every integer from 1 to $N$ exactly once. The integers in $A$ start in an arbitrary order. Besides the input order, the algorithm depends on two integers $P$ and $K$. The algorithm works as follows:

1. Partition $A$ into $K$ non-empty contiguous subarrays $A_1, A_2, \ldots, A_K$ such that concatenating them in order, $A_1A_2 \ldots A_K$, gives $A$.
2. Sort each subarray individually.
3. Choose at most $P$ of the subarrays, and swap any two of the chosen subarrays any number of times. Subarrays that are not chosen stay in place.

For example, let $A = [1\ 5\ 4\ 3\ 2]$ and $P = 2$. One possible partition into $K = 4$ subarrays is:

A1 = [1]
A2 = [5]
A3 = [4]
A4 = [3 2]

After sorting each subarray:

A1 = [1]
A2 = [5]
A3 = [4]
A4 = [2 3]

After swapping A4 and A2:

A1 = [1]
A2 = [2 3]
A3 = [4]
A4 = [5]

We want to show that the algorithm suits distributed environments. For a fixed input array and value of $P$, find the maximum number of subarrays $K$ such that, choosing the partition and the swaps wisely, the array ends up sorted.

The first line of the input gives the number of test cases, $T$.

$T$ test cases follow. Each test case consists of two lines. The first line contains two integers $N$ and $P$, as described above.

The second line contains $N$ integers $X_1, X_2, \ldots, X_N$ representing the array $A$.

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the maximum possible value of $K$.

• $1 \le T \le 100$
• $1 \le N \le 5000$
• $1 \le P \le 3$
• $1 \le X_i \le N$ for all $i$
• $X_i \ne X_j$ for all $i \ne j$

Case #1: the same as the walkthrough in the statement.

Case #2:

[4 5] [1 2 3]
Swap the two subarrays: [1 2 3] [4 5]

Case #3:

[6] [3 5 2 4] [1]
Sort [3 5 2 4], then swap [6] and [1]: [1] [2 3 4 5] [6]

Case #4:

[4 5] [1] [2 3]
Swap [4 5] and [1], then swap [2 3] and [4 5]: [1] [2 3] [4 5]

Case #5:

[1] [2] [6] [4] [5] [3]
Swap [6] and [3]: [1] [2] [3] [4] [5] [6]