Description

Maria 被 Ghastly Chemicals Junkies（GCJ）公司雇佣，帮助他们制造靶心（bullseye）。一个靶心由若干同心圆环（即圆心相同的圆环）组成，通常用作射箭靶。GCJ 只对黑白相间的靶心感兴趣。

Maria 拥有 $t$ 毫升的黑色油漆，她将用这些油漆绘制厚度为 $1\ \mathrm{cm}$（一厘米）的圆环。厚度为 $1\ \mathrm{cm}$ 的圆环指的是两个同心圆之间半径相差 $1\ \mathrm{cm}$ 的空间。

Maria 先在半径为 $r\ \mathrm{cm}$ 的白色圆外画上第一个黑色圆环。然后，只要油漆还够，她就不断重复如下过程：

1. Maria 想象在上一个黑色圆环外面有一个厚度为 $1\ \mathrm{cm}$ 的白色圆环。
2. 然后她在这个白色圆环外面再画一个厚度为 $1\ \mathrm{cm}$ 的黑色圆环。

注意，每一个“白色圆环”其实就是两条黑色圆环之间的空隙。

半径为 $1\ \mathrm{cm}$ 的圆盘面积是 $\pi\ \mathrm{cm}^2$。涂满面积为 $\pi\ \mathrm{cm}^2$ 需要 $1\ \mathrm{ml}$ 油漆。Maria 最多能画多少个黑色圆环？请注意：

• Maria 只会画完整的圆环。如果剩余油漆不足以画完整的黑色圆环，她会立即停止。
• 总会有足够的油漆画出至少一个黑色圆环。

Input Format

输入的第一行为测试用例数 $T$。接下来有 $T$ 个测试用例。每个测试用例一行，包含两个用空格分隔的整数 $r$ 和 $t$。

Output Format

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是 Maria 最多能画的黑色圆环数量。

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

Hint

限制条件

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

• $1 \leq T \leq 1000$
• $1 \leq r, t \leq 1000$

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

• $1 \leq T \leq 6000$
• $1 \leq r \leq 10^{18}$
• $1 \leq t \leq 2 \times 10^{18}$

翻译由 ChatGPT-4.1 完成。