Người bạn Cody-Jamal đang thực hiện tác phẩm sắp đặt nghệ thuật mới mang tên “Gallery of Pillars”. Tác phẩm sẽ được trưng bày trong một phòng triển lãm hình vuông kích thước \(N\) mét × \(N\) mét. Phòng được chia thành \(N^2\) ô vuông kích thước 1 mét × 1 mét, tạo thành ma trận \(N\times N\). Tâm chính xác của ô ở góc tây nam được gọi là điểm quan sát; người xem tác phẩm sẽ đứng tại đó. Mỗi ô còn lại chứa một cột trụ hình trụ. Mọi cột trụ có hai đáy tròn bán kính \(R\): một đáy nằm trên sàn tại tâm ô tương ứng, đáy còn lại chạm trần phòng. Người quan sát sẽ đứng tại điểm quan sát, ngắm \(N^2-1\) cột trụ và trầm trồ.

Cody-Jamal hiện đang tìm địa điểm để xem có thể chọn \(N\) lớn đến đâu. Anh cũng chưa quyết định vật liệu làm cột: có thể là bê tông hoặc ống nano carbon, nên bán kính đáy \(R\) có thể thay đổi từ 1 micromet đến gần nửa mét. Lưu ý rằng bán kính nửa mét sẽ khiến các cột kề nhau chạm nhau.

Là một nhà toán học được đào tạo bài bản, bạn nhanh chóng nhận ra có thể tồn tại những cột không thể nhìn thấy từ điểm quan sát. Cody-Jamal nhờ bạn xác định số cột nhìn thấy được với các tổ hợp \(N\) và \(R\) khác nhau. Một cách hình thức, một cột được nhìn thấy khi và chỉ khi tồn tại một đoạn thẳng từ tâm ô góc tây nam (điểm quan sát) đến một điểm bất kỳ trên biên cột đó mà không chạm hay cắt bất kỳ cột nào khác.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Tiếp theo là \(T\) dòng; mỗi dòng mô tả một bộ test bằng hai số nguyên \(N\) và \(R\). \(N\) là số ô vuông cạnh 1 mét theo mỗi chiều của phòng, còn \(R\) là bán kính mỗi cột tính bằng micromet. Do đó, bán kính cột tính bằng mét là \(R/10^6\).

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ 1), còn y là số cột trong tác phẩm nhìn thấy được từ điểm quan sát.

Ràng buộc

• \(1\le T\le100\).
• \(1\le R<10^6/2\).

Phân nhóm

• Test Set 1 (Hiển thị): \(2\le N\le300\).
• Test Set 2 (Ẩn): \(2\le N\le10^9\).

Đ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
4 100000
4 300000
3 300000
100 499999

Case #1: 9
Case #2: 7
Case #3: 5
Case #4: 3

Nguồn

Google Code Jam 2016, Chung kết thế giới, bài Gallery of Pillars.

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