Maria đã được công ty Ghastly Chemicals Junkies (GCJ) thuê để giúp họ sản xuất các bullseye (bia bắn). Một bullseye bao gồm một số vòng tròn đồng tâm (các vòng tròn có cùng tâm) và nó thường đại diện cho một bia bắn cung. GCJ quan tâm đến việc sản xuất các bullseye đen trắng.

Maria bắt đầu với \(t\) ml sơn đen, cô ấy sẽ sử dụng để vẽ các vòng tròn có độ dày \(1\) cm. Một vòng tròn có độ dày \(1\) cm là phần diện tích nằm giữa hai đường tròn đồng tâm có bán kính chênh lệch nhau \(1\) cm.

Maria vẽ vòng đen đầu tiên bao quanh một hình tròn trắng có bán kính \(r\) cm. Sau đó, cô ấy lặp lại quy trình sau miễn là cô ấy còn đủ sơn để thực hiện:

1. Maria tưởng tượng một vòng trắng có độ dày \(1\) cm bao quanh vòng đen cuối cùng.
2. Sau đó, cô ấy vẽ một vòng đen mới có độ dày \(1\) cm bao quanh vòng trắng đó.

Lưu ý rằng mỗi "vòng trắng" chỉ đơn giản là khoảng trống giữa hai vòng đen.

Diện tích của một hình tròn bán kính \(1\) cm là \(\pi\) cm\(^2\). Một ml sơn có thể phủ được diện tích \(\pi\) cm\(^2\). Hỏi số lượng vòng đen tối đa mà Maria có thể vẽ là bao nhiêu? Vui lòng lưu ý:

• Maria chỉ vẽ các vòng tròn hoàn chỉnh. Nếu lượng sơn còn lại không đủ để vẽ một vòng đen hoàn chỉnh, cô ấy sẽ dừng vẽ ngay lập tức.
• Luôn có đủ sơn để vẽ ít nhất một vòng đen.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ thử nghiệm, \(T\). \(T\) bộ thử nghiệm tiếp theo. Mỗi bộ thử nghiệm bao gồm một dòng chứa hai số nguyên cách nhau bởi dấu cách: \(r\) và \(t\).

Dữ liệu ra

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 vòng đen tối đa Maria có thể vẽ.

Ràng buộc

Phân nhóm 1 (Tập thử nghiệm 1 - Hiển thị)

• \(1 \le T \le 1000\).
• \(1 \le r, t \le 1000\).

Phân nhóm 2 (Tập thử nghiệm 2 - Ẩn)

• \(1 \le T \le 6000\).
• \(1 \le r \le 10^{18}\).
• \(1 \le t \le 2 \times 10^{18}\).

Phân nhóm

Các giới hạn của từng tập dữ liệu được nêu trong mục Ràng buộc.

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

5
1 9
1 10
3 40
1 1000000000000000000
10000000000000000 1000000000000000000

Case #1: 1
Case #2: 2
Case #3: 3
Case #4: 707106780
Case #5: 49

Nguồn

Google Code Jam 2013, Vòng 1A, bài Bullseye.

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