#P1450B. Balls of Steel
Balls of Steel
Description
You have distinct points on the plane and a non-negative integer parameter . Each point is a microscopic steel ball and is the attract power of a ball when it's charged. The attract power is the same for all balls.
In one operation, you can select a ball to charge it. Once charged, all balls with Manhattan distance at most from ball move to the position of ball . Many balls may have the same coordinate after an operation.
More formally, for all balls such that , we assign and .

Your task is to find the minimum number of operations to move all balls to the same position, or report that this is impossible.
The first line contains a single integer () — the number of test cases.
The first line of each test case contains two integers , (, ) — the number of balls and the attract power of all balls, respectively.
The following lines describe the balls' coordinates. The -th of these lines contains two integers , () — the coordinates of the -th ball.
It is guaranteed that all points are distinct.
For each test case print a single integer — the minimum number of operations to move all balls to the same position, or if it is impossible.
Input
The first line contains a single integer () — the number of test cases.
The first line of each test case contains two integers , (, ) — the number of balls and the attract power of all balls, respectively.
The following lines describe the balls' coordinates. The -th of these lines contains two integers , () — the coordinates of the -th ball.
It is guaranteed that all points are distinct.
Output
For each test case print a single integer — the minimum number of operations to move all balls to the same position, or if it is impossible.
Note
In the first test case, there are three balls at , , and and the attract power is . It is possible to move two balls together with one operation, but not all three balls together with any number of operations.
In the second test case, there are three balls at , , and and the attract power is . If we charge any ball, the other two will move to the same position, so we only require one operation.
In the third test case, there are four balls at , , , and , and the attract power is . We can show that it is impossible to move all balls to the same position with a sequence of operations.