#216628. [GKS 2016 #E] Sorting Array

We are in the process of creating a somewhat esoteric sorting algorithm to sort an array of all integers between and . The integers in can start in an arbitrary order. Besides the input order, the algorithm depends on two integers (which would be at most ) and . Here is how the algorithms works:

1. Partition into disjoint non-empty subarrays , , ..., such that such that concatenating them in order produces .
2. Sort each subarray individually.
3. Choose up to of the subarrays, and swap any two of them any number of times.

For example, consider and . A possible partition into disjoint 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 the algorithm is good for distributed environments by finding, for a fixed input and value of , the maximum number of partitions such that, choosing the partitions and swaps wisely, we can achieve a sorting of the original order. Can you help us to calculate that ?

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

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

The second line of the test case contains integers , , ..., represting array .

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

样例输入 1

5
5 2
1 5 4 3 2
5 2
4 5 1 2 3
6 2
6 3 5 2 4 1
5 3
4 5 1 2 3
6 3
1 2 6 4 5 3

样例输出 1

Case #1: 4
Case #2: 2
Case #3: 3
Case #4: 3
Case #5: 6

Case #1:

Same as walk through in the statement.

Case #2:

Swap the blocks:

Case #3:

Sort , then swap and , we get:

Case #4:

Swap and , then swap and :

Case #5:

Swap and :

Note: First sample cases would not appear in the Large dataset and the last sample cases would not appear in the Small dataset.

Limits

.

.

, for all .

for all .

Small dataset (Test set 1 - Visible)

.

Large dataset (Test set 2 - Hidden)

.