Bạn đang chờ trong một hàng dài để cắt tóc tại một tiệm tóc thời thượng. Tiệm có \(B\) thợ đang làm việc, được đánh số từ 1 đến \(B\). Thợ thứ \(k\) luôn mất đúng \(M_k\) phút để cắt tóc cho một khách và mỗi thợ chỉ có thể cắt tóc cho một khách tại một thời điểm. Ngay khi cắt xong, thợ lập tức rảnh để phục vụ khách khác.

Trong thời gian tiệm mở cửa, người đứng đầu hàng luôn đến thợ đang rảnh có số nhỏ nhất. Khi không có thợ nào rảnh, người đó chờ cho đến khi ít nhất một thợ rảnh.

Bạn là người thứ \(N\) trong hàng và tiệm vừa mở cửa. Thợ nào sẽ cắt tóc cho bạn?

Dữ liệu vào

Dòng đầu tiên chứa số bộ test \(T\). Mỗi bộ test gồm hai dòng. Dòng đầu chứa hai số nguyên cách nhau bởi dấu cách \(B\) và \(N\) — số thợ và vị trí của bạn trong hàng. Người đứng đầu hàng mang số 1, người kế tiếp mang số 2, v.v. Dòng thứ hai chứa \(M_1, M_2, \ldots, M_B\).

Dữ liệu ra

Với mỗi bộ test, in một dòng có dạng Case #x: y, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ 1) và \(y\) là số của thợ sẽ cắt tóc cho bạn.

Ràng buộc

• \(1 \le T \le 100\).
• \(1 \le N \le 10^9\).

Phân nhóm

• Nhỏ: \(1 \le B \le 5\); \(1 \le M_k \le 25\).
• Lớn: \(1 \le B \le 1000\); \(1 \le M_k \le 100000\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

3
2 4
10 5
3 12
7 7 7
3 8
4 2 1

Case #1: 1
Case #2: 3
Case #3: 1

Nguồn

Google Code Jam 2015, Vòng 1A, bài Haircut.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.