#2396 Haircut

1 s   128 MB  

Description

You are waiting in a long line to get a haircut at a trendy barber shop. The shop has B barbers on duty, and they are numbered 1 through B. It always takes the kth barber exactly Mk minutes to cut a customer's hair, and a barber can only cut one customer's hair at a time. Once a barber finishes cutting hair, he is immediately free to help another customer. While the shop is open, the customer at the head of the queue always goes to the lowest-numbered barber who is available. When no barber is available, that customer waits until at least one becomes available. You are the Nth person in line, and the shop has just opened. Which barber will cut your hair?

Input

The first line of the input gives the number of test cases, $T$. $T$ test cases follow; each consists of two lines. The first contains two space-separated integers $B$ and $N$ -- the number of barbers and your place in line. The customer at the head of the line is number 1, the next one is number 2, and so on. The second line contains $M_1, M_2, \dots, M_B$. $1 \leq B \leq 1000$ $1 \leq M_k \leq 100000$

Output

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 number of the barber who will cut your hair.

Sample Input

Sample Output

3
2 4
10 5
3 12
7 7 7
3 8
4 2 1
Case #1: 1
Case #2: 3
Case #3: 1

Source

Goole Code Jam Round 1A