3391：The Bug Sensor Problem

Mr. Macdonald is a farmer. He has a huge land to manage. To monitor the number of bugs in his land, he asks help from the famous professor T. Professor T is an expert on computer science.

Professor T studies several efficient approach and suggests Mr. Macdonald to setup a wireless sensor system in his land. The system will be setup as follows:

In each predefined location, one wireless sensor will be established. Since all sensors are operated by batteries, the powers consumed by the sensors are determined by the effective communication distance (ECD) between sensors. Mr. Macdonald is a nice old man. He prefers not to trouble professor T much. Therefore, he decides that all sensors will be set in the same power level. That is, all sensors will have the same effective communication distance.

The land is so huge that it is not possible to cover all spots by the sensors. However, each sensor can broadcast the collected data to their neighbors as long as the neighbors are in its effective communication distance. But the total number of sensors is relative small comparing to the land. Mr. Macdonald needs to travel the whole land to collect the data from sensors everyday.

Mr. Macdonald is getting old. He hopes that the computer in his house can collect all data from all sensors automatically. Again, he called professor T for help. This time, professor T suggests Mr. Macdonald to setup a base station in his house. The house is right in the center of the land.

Due to the limited budget, the number of receiver transmitter Mr. Macdonald can afford is limited and is relatively small comparing to the total number of sensors. It is impossible to assign receiver transmitter to every sensor. Therefore, sensors with no receiver transmitter need to send their data to the sensor with receiver transmitter (directly or indirect) first, After that, the sensor with receiver transmitter sends all data it receives from other sensors along with the data it collects back to the base station. You may assume that the receiver transmitter has enough power such that it always can send data back to the base station.

Professor T promises to write the necessary software to make all sensors work together in this way, but one important issue need to be studied. If all sensors are set at the maximum power level, all sensors might be able to send their data back without troubles, but the battery will be out-of-power soon. To save power, professor T need to decide the minimum power level needed such that the battery can have longest operating time while all sensor data can be collected by the base station.

Although professor T is good in programming, he is weak in algorithm design. Your goal is to help professor T to write a program to determine the minimum power level needed to set all sensors accordingly. To simplify our problem, please report the ECD corresponding to the minimum power level. Please apply the ceiling function to your answer.

Here is an example:

Assume that the land is 10 × 10. There are three sensors, located at (1,1), (2,1) and (8,7). We also assume that there are 2 receiver transmitters. In this example, the ECD of all sensors need to be set at 1.

The first line contains the number of test cases w, 1 ≤ w ≤ 10. Then the w test cases are listed one by one. In each test case, the first line is a single integer, representing the number of receiver transmitters for that test case. After that, the test case consists of some lines with two numbers each line:

X Y

Here two numbers are separated by a single blank, X is an integer, denoting the x-coordinate of the sensor, and Y is also an integer, denoting the y-coordinate of the same sensor. Each test case is ended by the following line: −1.

Please note that the land is a rectangle with dimensions 100000 × 100000.

For each test case, output the corresponding ECD.