Map Labeler

Time limit1sMemory limit128 MB

Summary

Given city points in the plane, find the largest square label size so that each label has its city at the midpoint of its top or bottom edge and no two label interiors overlap.

Level: Hard8 of 10
Topics: Binary search, Geometry, Implementation, Brute force
Solved: No attempts yet

Problem

Generating a map is a hard problem in cartography, and one crucial part of it is labeling the cities automatically: every city needs a text label placed at its location so that no two labels overlap. In this problem we consider a simplified version of that task.

Model each city as a point in the plane. Its label is a text contained in a square whose edges are parallel to the $x$ - and $y$ -axes. Each label must be positioned so that the city's point lies exactly at the midpoint of the label's top or bottom edge. In a valid labeling all square labels have the same size, and no two labels overlap in their interiors, although they may touch along an edge.

Given the integer coordinates of every city, find the largest integer label size for which a valid labeling exists.

Input

The first line contains an integer $t$ ( $1 \le t \le 10$ ), the number of test cases. Each test case begins with a line containing an integer $m$ ( $3 \le m \le 100$ ), the number of cities. Each of the following $m$ lines contains two integers $X$ and $Y$ ( $-10000 \le X, Y \le 10000$ ), the $x$ - and $y$ -coordinates of one city. No two cities share the same coordinates.

Output

For each test case, print one line containing the maximum possible integer label size for a valid labeling.

Examples3

Example 1
Input
```
1
6
1 1
2 3
3 2
4 4
10 4
2 5
```
Expected output
```
2
```
Example 2
Input
```
1
3
0 0
0 10
0 30
```
Expected output
```
20
```
Example 3
Input
```
1
3
0 0
100 0
200 0
```
Expected output
```
200
```