Barber Shop Queue

You are waiting in a long line for a haircut at a popular barber shop. The shop has $B$ barbers on duty, numbered 1 through $B$. Barber $k$ always takes exactly $M_k$ minutes to cut one customer's hair, and a barber cuts only one customer's hair at a time. As soon as a barber finishes, he takes the next customer.

The customer at the head of the line goes to the free barber with the smallest number. If no barber is free, that customer waits until one becomes free.

You are the $N$th person in line, and the shop has just opened. Find the number of the barber who will cut your hair.

The first line contains the number of test cases $T$. $T$ test cases follow, and each one consists of two lines.

The first line contains the number of barbers $B$ and your place in line $N$, separated by a space. 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$, separated by spaces.

Limits

• $1 \le T \le 100$
• $1 \le B \le 1000$
• $1 \le N \le 10^9$
• $1 \le M_k \le 100000$

For each test case, print one line in the form 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.

Consider the first example case. You are the fourth customer, barber 1 takes 10 minutes and barber 2 takes 5 minutes. The moment the shop opens, the first customer can choose between barbers 1 and 2, so she goes to barber 1, the smaller number. The second customer goes straight to barber 2. The third customer waits because no barber is free. After 5 minutes barber 2 finishes the second customer and takes the third one. After 10 minutes barbers 1 and 2 both become free, and you are next, so you choose barber 1 out of the two.