Map Labeler#6845
Map generation is a difficult task in cartography. A vital part of this task is the automatic labeling of cities on a map; for each city, there is a text label attached to its location so that no two labels overlap. In this problem, we consider a simple variant of the automatic map labeling problem.
Assume that each city is represented as a point on the plane, and its label is a text bounded by a square with edges parallel to the - and -axes. The label of each city must be positioned such that the city point appears exactly in the middle of either the top or bottom edge of the label. In a good labeling, all square labels have the same size, and no two labels overlap, although they may share an edge. Figure 1 shows an example of a good labeling (the texts of the labels are not shown).
Figure 1
The first line contains a single integer (1 \leq t \leq 10), the number of test cases. Each test case starts with a line containing an integer (3 \leq m \leq 100), the number of cities. Then lines follow, each containing a pair of integers: the coordinates and (-10000 \leq x, y \leq 10000) of a city on the map. No two cities have the same coordinates.
For each test case, print on a separate line the maximum possible label size (an integer) for which a good labeling exists for the map.
Example 1