Description

你的朋友 Cody-Jamal 正在筹备他的新艺术装置“柱廊美术馆”。这个装置将在一个边长为 $\mathbf{N}$ 米的正方形美术馆中展出。美术馆被划分为 $\mathbf{N}^2$ 个 $1 \times 1$ 米的方格，组成一个 $\mathbf{N} \times \mathbf{N}$ 的矩阵。西南角单元格的正中心被称为“观景点”；观众应站在这里欣赏作品。其余每个格子里都竖立着一根圆柱形立柱。所有立柱都有两个半径为 $\mathbf{R}$ 的圆形底面：一个底面落在地板上，位于对应格子的正中心，另一个底面顶到美术馆的天花板。观众将站在观景点，欣赏 $\mathbf{N}^2-1$ 根立柱。

Cody-Jamal 目前正在考察场地，试图确定 $\mathbf{N}$ 的最大可能值。同时，他还没有决定立柱的材质——可能是混凝土，也可能是碳纳米管，因此每根立柱的底面半径 $\mathbf{R}$ 可能从 1 微米到接近半米不等。注意，如果半径达到半米，相邻的立柱就会相互接触。

你作为一名训练有素的数学家，很快就发现有些立柱可能无法从观景点看到。Cody-Jamal 请你帮忙，判断在不同的 $\mathbf{N}$ 和 $\mathbf{R}$ 组合下，从观景点能看到多少根立柱。形式化地说，某根立柱是可见的，当且仅当存在一条从西南角单元格中心（观景点）到该立柱边界上任意一点的直线段，且这条线段不与其他任何立柱相交或接触。

Input Format

输入的第一行包含一个整数 $\mathbf{T}$，表示测试用例数量。接下来有 $\mathbf{T}$ 行，每行描述一个测试用例，包含两个整数 $\mathbf{N}$ 和 $\mathbf{R}$。$\mathbf{N}$ 表示美术馆在每个方向上的方格数，$\mathbf{R}$ 表示每根立柱的半径，单位为微米。因此，每根立柱的半径为 $\mathbf{R}/10^6$ 米。

Output Format

对于每组测试用例，输出一行 Case #x: y，其中 $x$ 为测试用例编号（从 1 开始），$y$ 为从观景点能看到的立柱数量。

4
4 100000
4 300000
3 300000
100 499999

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

Hint

样例解释

下图展示了前两个样例的示意（非真实比例）。黑色圆圈中心为观众，其余圆圈为立柱，灰色为可见立柱，红色为不可见立柱。蓝色虚线表示部分无遮挡的视线，红色虚线表示被阻挡的视线（在首次被阻挡处变为灰色）。

限制条件

• $1 \leqslant \mathbf{T} \leqslant 100$。
• $1 \leqslant \mathbf{R} < 10^6/2$。

小数据集（10 分，测试集 1 - 可见）

• $2 \leqslant \mathbf{N} \leqslant 300$。

大数据集（30 分，测试集 2 - 隐藏）

• $2 \leqslant \mathbf{N} \leqslant 10^9$。

翻译由 GPT4.1 完成。