{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eMap generation is a difficult task in cartography. A vital part of such task is automatic labeling of the cities in a map; where for each city there is text label to be attached to its location, so that no two labels overlap. In this problem, we are concerned with a simple case of automatic map labeling.\u003c/p\u003e\n\u003cp\u003eAssume that each city is a point on the plane, and its label is a text bounded in a square with edges parallel to x and y axis. The label of each city should be located such that the city point appears exactly in the middle of the top or bottom edges of the label. In a good labeling, the square labels are all of the same size, and no two labels overlap, although they may share one edge. Figure 1 depicts an example of a good labeling (the texts of the labels are not shown.)\u003c/p\u003e\n\u003cp\u003eGiven the coordinates of all city points on the map as integer values, you are to find the maximum label size (an integer value) such that a good labeling exists for the map.\u003c/p\u003e\n\u003cp\u003e\u003cb\u003eInput Specification\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003eThe first line contains a single integer t (1 \u0026lt;\u003d t \u0026lt;\u003d 10), the number of test cases. Each test case starts with a line containing an integer m (3 \u0026lt;\u003d m \u0026lt;\u003d 100), the number of cities followed by m lines of data each containing a pair of integers; the first integer (X) is the x and the second one (Y) is the y coordinates of one city on the map (-10000 \u0026lt;\u003d X, Y \u0026lt;\u003d 10000). Note that no two cities have the same (x, y) coordinates.\u003c/p\u003e\n\u003ccenter\u003e\u003cimg src\u003d\"CDN_BASE_URL/94e18b554d29109129d417669202d909?v\u003d1716705977\"\u003e\u003c/center\u003e\n\u003cp\u003e\u003cb\u003eOutput Specification\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003eThe output will be one line per each test case containing the maximum possible label size (an integer value) for a good labeling.\u003c/p\u003e\n\u003cp\u003e\u003cb\u003eSample Input\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003e\u003c/p\u003e\u003cpre\u003e1\n6\n1 1\n2 3\n3 2\n4 4\n10 4\n2 5\n\u003c/pre\u003e\u003cp\u003e\u003c/p\u003e\n\u003cp\u003e\u003cb\u003eSample Output\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003e\u003c/p\u003e\u003cpre\u003e2\n\u003c/pre\u003e\u003cp\u003e\u003c/p\u003e\n"}}]}