Sorting Array (Small)

We are building a somewhat unusual algorithm that sorts an array $A$ containing every integer from 1 to $N$ exactly once. The elements of $A$ start in an arbitrary order. Besides the input order, the algorithm depends on two integers $P$ and $K$, where $P$ is at most 3. Here is how it works.

1. Split $A$ into $K$ non-empty subarrays $A_1, A_2, \dots, A_K$ so that concatenating them in order as $A_1 A_2 \dots A_K$ gives back $A$.
2. Sort each subarray on its own.
3. Choose at most $P$ of the subarrays, then swap the places of two chosen subarrays as many times as you want.

For example, take $A = [1\ 5\ 4\ 3\ 2]$ and $P = 2$. One way to split it 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 and a fixed $P$, find the largest $K$ for which a careful choice of the split and the swaps sorts the original array.

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 the two integers $N$ and $P$ described above. The second line contains $N$ integers $X_1, X_2, \dots, 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 largest possible value of $K$.

• $1 \le T \le 100$
• $1 \le N \le 5000$
• $1 \le X_i \le N$ for every $i$
• $X_i \ne X_j$ whenever $i \ne j$
• $P = 2$

The first test case of the example input is the walkthrough given in the statement.

The second test case is split like this.

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

The third test case is split like this.

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