平面上有 $$$n$$$ 个不同点 $$$(x_1, y_1),\ldots,(x_n,y_n)$$$ 和一个非负整数参数 $$$k$$$。每个点都是一个微小的钢球,$$$k$$$ 是钢球充电时的吸引力。所有球的吸引力都相同。
在一次操作中,您可以选择一个球 $$$i$$$ 为其充电。一旦充电,所有与球 $$$i$$$ 曼哈顿距离最多 $$$k$$$ 的球都会移动到球 $$$i$$$ 的位置。一次操作后,许多球可能具有相同的坐标。
更正式地说,对于所有球 $$$j$$$ 使得 $$$|x_i - x_j| + |y_i - y_j| \le k$$$,我们分配 $$$x_j:=x_i$$$ 和 $$$y_j:=y_i$$$。
操作示例。在中心的球充电后,另外两个球移动到其位置。右边,中间的红点就是这些球的共同位置。
你的任务是找到将所有球移动到同一位置的最少操作次数,或者报告这是不可能的。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。
每个测试用例的第一行包含两个整数 $$$n$$$, $$$k$$$ ($$$2 \le n \le 100$$$, $$$0 \le k \le 10^6$$$) - 分别是球的数量和所有球的吸引力。
以下 $$$n$$$ 行描述了球的坐标。这些行中的第 $$$i$$$ 包含两个整数 $$$x_i$$$、$$$y_i$$$ ($$$0 \le x_i, y_i \le 10^5$$$) — 第 $$$i$$$ 球的坐标。
保证所有点都是不同的。
输出
对于每个测试用例,打印一个整数 - 将所有球移动到同一位置的最小操作数,如果不可能,则打印 $$$-1$$$。
示例
输入 #1
3 3 2 0 0 3 3 1 1 3 3 6 7 8 8 6 9 4 1 0 0 0 1 0 2 0 3
输出 #1
-1 1 -1
注意
在第一个测试用例中,有三个球,分别位于 $$$(0, 0)$$$、$$$(3, 3)$$$ 和 $$$(1, 1)$$$,吸引力为 $$$2$$$。可以通过一次操作来移动两个球,但不能通过任意次数的操作来移动所有三个球。
在第二个测试用例中,有三个球,分别位于 $$$(6, 7)$$$、$$$(8, 8)$$$ 和 $$$(6, 9)$$$,吸引力为 $$$3$$$。如果我们对任何一个球进行冲锋,另外两个球就会移动到相同的位置,因此我们只需要一次操作。
在第三个测试用例中,有四个球分别位于$$$(0, 0)$$$、$$$(0, 1)$$$、$$$(0, 2)$$$和$$$(0, 3)$$$,吸引力为$$$1$$$。我们可以证明,不可能通过一系列操作将所有球移动到同一位置。