你正在为 Apricot Rules LLC 的无人驾驶直接配送无人机方向设计部门工作。公司即将推出其首款无人机“Principia”。你的任务是为 Principia 设计备份系统，以防它失去对主要地理定位系统（如 GPS）的访问权限，但它仍然需要一种获取方向的方法。Principia 设计用于平坦区域；形式上，该区域是一个笛卡尔平面，坐标单位为米。平面上有一个或多个点是无人机维修中心。没有两个维修中心位于同一位置。

Principia 有一个系统，可以检索其位置 $L_1$ 距离（也称为曼哈顿距离）在 $D$ 米以内的维修中心的相对位置。检索到的信息是相对于 Principia 当前位置的一组维修中心位置。例如：“有一个维修中心在北侧 4 米、西侧 3.5 米处，另一个在东侧 2.5 米处”。请注意，该信息不会识别具体的维修中心；它只给出相对于 Principia 的位置。

你很快意识到，地图上可能存在一些点，这些信息不足以让 Principia 唯一确定其当前位置。这是因为可能存在两个（或更多）不同的点，从这些点看去，信息看起来是一样的。具有此属性的点称为“不可区分点”（non-distinguishable），而所有其他点称为“可区分点”（distinguishable）。

形式上，当 Principia 位于点 $(x, y)$ 时检索到的信息为 $\text{Info}(x, y) :=$ 所有点 $(z - x, w - y)$ 的集合，其中 $(z, w)$ 是维修中心的位置，且 $|z - x| + |w - y| \le D$。这里 $|z - x|$ 和 $|w - y|$ 分别表示 $z - x$ 和 $w - y$ 的绝对值。当且仅当存在另一个点 $(x_2, y_2)$ 使得 $\text{Info}(x_1, y_1) = \text{Info}(x_2, y_2)$ 时，点 $(x_1, y_1)$ 是不可区分的。

例如，假设 $D=4$，维修中心位于点 $(0, 0)$ 和 $(5, 0)$。点 $(0, 0)$ 是不可区分的，因为 $\text{Info}(0, 0) = \{(0, 0)\} = \text{Info}(5, 0)$。这意味着点 $(5, 0)$ 也是不可区分的。另一方面，$\text{Info}(3.5, 0.1) = \{(-3.5, -0.1), (1.5, -0.1)\}$ 不等于任何其他点的信息，这意味着点 $(3.5, 0.1)$ 是可区分的。下图展示了可区分点（红色）和不可区分点（蓝色）的区域：

Principia 被部署到一个点，该点是从所有距离至少一个维修中心 $D$ 米以内（使用 $L_1$ 距离）的点集中均匀随机选择的——也就是说，是所有满足 $\text{Info}(x, y)$ 非空的点 $(x, y)$ 的集合。该选择属于给定连续点集 $S$ 的概率与 $S$ 的面积（平方米）成正比。在上面的例子中，每个红色正方形的面积为 4.5 平方米，而每个蓝色部分的面积为 23 平方米。因此，Principia 被部署在每个红色正方形内的概率是 $4.5 / (3 \times 4.5 + 2 \times 23)$，被部署在每个蓝色部分内的概率是 $23 / (3 \times 4.5 + 2 \times 23)$。由于相邻不同颜色区域之间的边界面积为 0，因此 Principia 被部署在边界上的概率恰好为 0。

给定所有维修中心的位置，Principia 被部署到的点是可区分点的概率是多少？

输入格式

第一行输入包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含两个整数 $N$ 和 $D$，分别表示维修中心的数量和 Principia 可以从维修中心检索信息的最大 $L_1$ 距离。接下来有 $N$ 行，第 $i$ 行包含两个整数 $X_i$ 和 $Y_i$，表示第 $i$ 个维修中心的坐标。所有坐标和 $D$ 的单位均为米。

输出格式

对于每个测试用例，输出一行 Case #x: y z，其中 $x$ 是测试用例编号（从 1 开始），$y$ 和 $z$ 是非负整数。分数 $y/z$ 必须表示如果从所有距离至少一个维修中心 $D$ 米以内（使用 $L_1$ 距离）的位置中均匀随机选择一个位置，Principia 处于可区分位置的概率。如果有多个可接受的 $y$ 和 $z$ 值，请选择使 $z$ 最小化的那组值。

数据范围

内存限制：1GB。 $1 \le T \le 100$。 $1 \le D \le 10^7$。 $-10^9 \le X_i \le 10^9$，对于所有 $i$。 $-10^9 \le Y_i \le 10^9$，对于所有 $i$。 $(X_i, Y_i) \neq (X_j, Y_j)$，对于所有 $i \neq j$（没有两个维修中心位于同一位置）。

样例

样例输入 1

4
2 4
0 0
5 0
2 1
0 0
5 0
2 4
0 0
4 4
2 4
0 0
5 1

样例输出 1

Case #1: 27 119
Case #2: 0 1
Case #3: 0 1
Case #4: 1 5