你的朋友 Cody-Jamal 正在筹备他的新艺术装置，名为“柱廊”（Gallery of Pillars）。该装置将在一个 $N \times N$ 米的方形画廊中展出。画廊被划分为 $N^2$ 个 $1 \times 1$ 米的正方形，形成一个 $N \times N$ 的矩阵。西南角单元格的精确中心被称为“观察点”；参观者应站在那里欣赏艺术品。其余每个单元格中都包含一根圆柱形柱子。所有柱子都有两个半径为 $R$ 的圆形底面：一个位于地板上，处于其对应单元格的中心；另一个接触画廊的天花板。观察者将站在观察点，观察其余的 $N^2 - 1$ 根柱子。

Cody-Jamal 目前正在考察场地，试图确定他能将 $N$ 的值设为多大。此外，他还没有决定柱子将由什么材料制成；可能是混凝土，也可能是碳纳米管，因此每根柱子底座的半径 $R$ 可能从 $1$ 微米到接近半米不等。注意，半米的半径会使相邻的柱子接触。

作为一名训练有素的数学家，你很快观察到，有些柱子可能无法从观察点看到。Cody-Jamal 请你帮忙确定，对于不同的 $N$ 和 $R$ 组合，可见柱子的数量。形式上，如果存在一条从西南角单元格中心（观察点）出发，到达柱子边界上任意一点的直线段，且该线段不接触或穿过任何其他柱子，则称该柱子是可见的。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 行，每行描述一个不同的测试用例，包含两个整数 $N$ 和 $R$。$N$ 是画廊每一维上 $1$ 米见方单元格的数量，$R$ 是每根柱子的半径（单位为微米）。因此，$R / 10^6$ 即为每根柱子以米为单位的半径。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是从观察点可见的柱子数量。

数据范围

时间限制：每个测试集 20 秒。 内存限制：1 GB。 $1 \le T \le 100$。 $1 \le R < 10^6 / 2$。

小型数据集（测试集 1 - 可见） $2 \le N \le 300$。

大型数据集（测试集 2 - 隐藏） $2 \le N \le 10^9$。

样例

样例输入 1

4
4 100000
4 300000
3 300000
100 499999

样例输出 1

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

说明

下图展示了前两个样例（未按比例绘制）。黑圆中心是观察者。其他圆圈是柱子，可见的用灰色表示，不可见的用红色表示。蓝色虚线代表部分未被遮挡的视线；红色虚线代表被遮挡的视线（在首次被遮挡的点处变为灰色）。