Indonesia is developing a technology which can utilize echo signal (although, the purpose of this technology is still unknown). Let there be N stations scattered in a 2D plane. Each station is both a sensor and a sender. The technology allows us to send an initial signal at a specific location (xinit, yinit), and it will spread like a sound signal such that all stations which are no more than radius of R from (xinit, yinit) will receive the signal. Upon receiving the initial signal, each station will send an echo signal with a radius of R from its location. Each affected station will record the received echo signal. Note that a station may receive and record more than one echo signal, e.g., from two or more of its neighbors stations.
After playing around with the technology, the researchers are interested with the largest number of echo signal records that can be made by any station. The researchers impose another restriction: the initial signal can only be sent to (x, y) where x and y are integers. Why? We don't know; researchers have strange mind.
Consider the following example of 5 stations at A:(2, 2), B:(1, 5), C:(9, 5), D:(5, 6), and E:(9, 11). Supposed the radius R = 5, then we can send the initial signal to (5, 4), triggering the first four stations (A, B, C, and D) to send echo signals.
In this example, we can get a station to record 3 echo signals, and this is the highest possible number of echo signals can be recorded by any station in this example. Note that there are also other intial signal location which can cause a station to record 3 echo signals in this example, e.g., (4, 5), (5, 3) (5, 5), (5, 6), (6, 5), etc., but none can make a station to record 4 echo signals.
Given the coordinate of N stations and the radius of intial and echo signal, find the coordinate (which both x and y are integers) of initial signal which cause a station to record the highest possible number of echo signals; output only the number of echo signals.
Input begins with an integer: T (1 ≤ T ≤ 20) denoting the number of cases.
Each case contains the following input block: Each case begins with two integers: N R (1 ≤ N ≤ 2,000; 1 ≤ R ≤ 1,000,000) denoting the number of stations and the signal's radius, respectively. The next N lines, each contains two integers: xi yi (-1,000,000 ≤ xi, yi ≤ 1,000,000) representing the coordinate of each station.
For each case, output in a line "Case #X: Y" where X is the case number (starts from 1) and Y is the output for the respective case.
2 5 5 2 2 1 5 9 5 5 6 9 11 4 1000000 0 0 100 0 0 100 100 100
Case #1: 3 Case #2: 3
Case 1: This is the example given in the problem statement.
Case 2: The signal's radius is very large while the stations are close to each other. Just send the initial signal anywhere nearby the stations, e,g. at (50, 50), and all stations will receive the initial signal. Each station then will send echo signals to any other stations within radius, thus, each station will record 3 echo signals (1 from each other stations).
End of Problem