Việc sở hữu một cửa hàng kẹo thật khó khăn! Bạn phải tối ưu hóa đủ mọi thứ. Gần đây, bạn đang bán một loại kẹo rất phổ biến gọi là Whizboppers. Những loại kẹo này rất nhanh hỏng, dẫn đến các đặc điểm sau:

• Bạn phải mua Whizboppers mới từ nhà cung cấp vào mỗi sáng.
• Bạn phải bán Whizboppers trong chính các hộp mà bạn đã mua từ nhà cung cấp sáng hôm đó.

Bạn có thể đặt hàng Whizboppers từ nhà cung cấp theo các hộp chứa bất kỳ số nguyên gam kẹo nào.

Mỗi ngày có tối đa \(k\) người đến cửa hàng của bạn, và bắt đầu từ người đầu tiên, họ sẽ chọn một số nguyên xu để chi cho Whizboppers: trong khoảng từ 1 đến \(C\) xu (bao gồm cả hai đầu). Bạn sẽ bán Whizboppers với giá 1 xu mỗi gam; vì vậy nếu một người muốn chi 4 xu, bạn sẽ đưa cho người đó đúng 4 gam kẹo. Bạn có thể thực hiện việc này bằng cách đưa cho họ một hộp 4 gam, hoặc có thể là một hộp 2 gam và hai hộp 1 gam.

Số lượng hộp tối thiểu bạn cần đặt hàng là bao nhiêu để bất kể mỗi người đặt mua bao nhiêu, bạn luôn có thể đưa cho tất cả mọi người khối lượng Whizboppers mà họ muốn?

Lưu ý: Khi một người chọn mua bao nhiêu kẹo, bạn biết những người khác đã mua gì trước đó, nhưng bạn không biết những người tiếp theo sẽ mua gì.

Ví dụ, nếu có tối đa 2 người đến cửa hàng mỗi ngày và mỗi người chi tối đa 2 xu (\(k=2, C=2\)), bạn có thể mua bốn hộp 1 gam từ nhà cung cấp. Nhưng bạn có thể làm tốt hơn: nếu bạn mua hai hộp 1 gam và một hộp 2 gam, bạn có thể làm hài lòng khách hàng của mình. Đây là cách thực hiện:

First Person   Boxes given   Second Person   Boxes given
--------------------------------------------------------
  2 cents      1 x 2-gram      2 cents       2 x 1-gram
                               1 cent        1 x 1-gram
  -----------------------------------------------------
  1 cent       1 x 1-gram      2 cents       1 x 2-gram
                               1 cent        1 x 1-gram

Bất kể người đầu tiên đặt hàng bao nhiêu, bạn có thể đưa ra các hộp sao cho người thứ hai vẫn có thể nhận được đúng lượng kẹo cần thiết. Vì vậy, với \(k=2, C=2\), bạn có thể phục vụ bất kỳ chuỗi đơn hàng nào với 3 hộp.

Dữ liệu vào

Dòng đầu tiên của đầu vào cho biết số lượng bộ thử nghiệm, \(T\). \(T\) dòng tiếp theo, mỗi dòng chứa hai số nguyên: \(k\) và \(C\), số lượng người tối đa và số xu tối đa mỗi người có thể chi tiêu.

Dữ liệu ra

Đối với mỗi bộ thử nghiệm, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ thử nghiệm (bắt đầu từ 1) và y là số lượng hộp tối thiểu bạn cần đặt hàng mỗi ngày.

Ràng buộc

• \(1 \le T \le 100\).

Phân nhóm

• Small dataset (Test set 1): \(1 \le k \le 20, 1 \le C \le 3\).
• Large dataset (Test set 2): \(1 \le k \le 1000, 1 \le C \le 10^{12}\).

Đ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ụ

4
1 5
2 2
10 3
2 50

Case #1: 3
Case #2: 3
Case #3: 19
Case #4: 11

Nguồn

Google Code Jam 2010, Chung kết thế giới, bài Candy Store.

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