이발

당신은 인기 있는 이발소에서 머리를 자르기 위해 긴 줄에서 기다리고 있다. 가게에서는 B명의 이발사가 근무 중이며, 이들에게는 1부터 B까지 번호가 매겨져 있다. k번째 이발사가 고객 한 명의 머리를 자르는 데에는 항상 정확히 $M_{k}$분이 걸리며, 이발사 한 명은 한 번에 고객 한 명의 머리만 자를 수 있다. 이발사는 머리 자르기를 마치는 즉시 다른 고객을 도울 수 있다.

가게가 영업하는 동안에는 줄 맨 앞의 고객이 항상 이용 가능한 이발사 중 번호가 가장 작은 이발사에게 간다. 이용 가능한 이발사가 없으면, 그 고객은 적어도 한 명의 이발사를 이용할 수 있게 될 때까지 기다린다.

당신은 줄의 N번째 사람이고, 가게는 방금 문을 열었다. 어느 이발사가 당신의 머리를 자르게 되는가?

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100. 1 ≤ N ≤ $10^{9}$.

작은 데이터 세트

시간 제한: 240초. 1 ≤ B ≤ 5. 1 ≤ $M_{k}$ ≤ 25.

큰 데이터 세트

시간 제한: 480초. 1 ≤ B ≤ 1000. 1 ≤ $M_{k}$ ≤ 100000.

입력의 첫째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어지며, 각 테스트 케이스는 두 줄로 이루어진다. 첫째 줄에는 공백으로 구분된 두 정수 B와 N, 즉 이발사의 수와 줄에서 당신의 순서가 주어진다. 줄 맨 앞의 고객 번호는 1이고, 그다음 고객의 번호는 2이며, 이런 식으로 이어진다. 둘째 줄에는 $M_{1}$, $M_{2}$, ..., $M_{B}$가 주어진다.

각 테스트 케이스마다 "Case #x: y"을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 당신의 머리를 자를 이발사의 번호이다.

케이스 #1에서 당신은 줄의 네 번째 사람이며, 이발사 1과 2은 머리를 자르는 데 각각 10분과 5분이 걸린다. 가게가 문을 열면 첫 번째 고객은 즉시 이발사 1과 2 중에서 선택할 수 있으며, 번호가 가장 작은 이발사인 1을 선택한다. 두 번째 고객은 즉시 이발사 2에게 서비스를 받는다. 세 번째 고객은 더 이상 한가한 이발사가 없으므로 기다린다. 5분 후, 이발사 2이 두 번째 고객의 머리 자르기를 마치고 세 번째 고객에게 서비스를 제공한다. 10분 후, 이발사 1과 2 모두 작업을 마친다. 이제 당신 차례이며, 이발사 1과 2 중에서 선택할 수 있고, 1을 선택한다.