ACM-ICPC Indonesia National Contest 2013

Problem F

PASS Me Not

Time Limit: 3 seconds

Given a sequence of N unique integers, you should choose K integers from the sequence in one or more PASS such that each integer you choose is strictly larger than any previous integer that has been chosen.

One PASS consists of reading and considering each number one by one strictly from left to right.

For example, let A = {2, 5, 6, 1, 4, 3} and K = 4. There are couple ways to achieve the goals:

1^st PASS: 2 3    {2, 5, 6, 1, 4, 3}
2^nd PASS: 4      {2, 5, 6, 1, 4, 3}
3^rd PASS: 5      {2, 5, 6, 1, 4, 3}

Here we performed 3 PASSes: {2, 3}, {4}, {5} and the chosen sequence of integers is: 2, 3, 4, 5.

```
1^st PASS: 1
2^nd PASS: 2 3
3^rd PASS: 5
```
Here we performed 3 PASSes: {1}, {2, 3}, {5}.
```
1^st PASS: 1 3
2^nd PASS: 5 6
```
Here we performed 2 PASSes: {1, 3}, {5, 6}. Apparently, this corresponds to the minimum number of PASS we need to achieve the goal.

...and many other ways

In the example above, the minimum number of PASS we need to achieve the goal is 2 (shown by 3^rd example).

Your goal in this problem is to find the minimum number of PASS needed to achieve the goal, i.e. choosing K integers from the given sequence such that each integer you choose is strictly larger than any previous integers that has been chosen.

Input

The first line of input contains an integer T (1 ≤ T ≤ 50) the number of cases. Each case begins with two integers N and K (1 ≤ K ≤ N ≤ 2,000; K ≤ 100). The next line contains N integers A_i (1 ≤ A_i ≤ 1,000,000,000) representing the given sequence of integers. You may assume all integers in the sequence are unique.

Output

For each case, output in a line the "Case #X: Y" where X is the case number starts from 1, and Y is the minimum number of PASS needed to achieve the goal for that case.

Sample Input	Output for Sample Input
4 6 4 2 5 6 1 4 3 6 3 2 5 6 1 4 3 5 5 5 4 3 2 1 6 6 2 3 6 1 4 5	Case #1: 2 Case #2: 1 Case #3: 5 Case #4: 3

Explanation for the 2^nd sample input.

The longest increment subsequence of {2, 5, 6, 1, 4, 3} is {2, 5, 6} which already has a length of 3. So, we only need one PASS to achieve the goal.

Explanation for the 3^rd sample input.

The sequence is given in decreasing order, so we can only choose one integer in each PASS.

Explanation for the 4^th sample input.

The corresponding PASS: {1}, {2, 3, 4, 5}, {6}