Haircut Queue

A long line has formed outside a fashionable barber shop, and you are standing in it. The shop has $B$ barbers on duty, numbered 1 through $B$. The $k$th barber always takes exactly $M_k$ minutes to cut one customer's hair, and can only cut one customer's hair at a time. As soon as a barber finishes, that barber takes the next customer.

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

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

The first line contains the number of test cases $T$. Each test case then follows on two lines. The first line of a test case 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$, separated by spaces.

Limits

• $1 \le T \le 100$
• $1 \le N \le 10^9$
• $1 \le B \le 5$
• $1 \le M_k \le 25$

For each test case, print one line in the format Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the number of the barber who cuts your hair.

Take the case $B = 2$, $N = 4$, $M_1 = 10$, $M_2 = 5$. The moment the shop opens, the first customer can choose between barbers 1 and 2, so she takes the lower number, barber 1. 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. At minute 10 barbers 1 and 2 finish together, and you are next in line, so you choose between them and take barber 1.