Thousands of years ago, the kingdom of Westeros decided to build a wall to deter invaders. The wall was an incredible feat of engineering, but it proved to have a major weakness: there are long stretches of the wall with no villages nearby. For these stretches of the wall, it was difficult to supply the guards and hence difficult to respond to attacks.

In the present day, historians who have been studying the wall wonder if it could have been built in a way that mitigates this weakness. Specifically, they are interested in the minimum number $D$ such that one could build a wall where the length of each wall section between two villages is at most $D$.

The land of Westeros can be mapped on a 2-D grid. There are $N$ villages located at integer coordinates on the grid. The wall starts at a given start village and can run between adjacent coordinates until it reaches some given end village. Coordinates are adjacent if their $X$ and $Y$ values differ by at most one (so up/down/left/right and diagonally). The length of the wall between adjacent coordinates is one unit (even diagonally).

The wall does not have to visit every village, but passing through villages between the start and end may reduce the length $D$.

Input Specification

The input will contain 10 datasets. Each dataset begins with an integer $N$ $(2\le N\le 100000)$, the number of villages. The next $N$ lines each contain two integers $X_i$, $Y_i$ $(0\le X_i,Y_i\le {10}^9)$, the coordinates of each village. The wall should start at the first village and end at the last village.

For the first 3 datasets, $N\le 50$.
For the first 6 datasets, $N\le 1000$.

Output Specification

For each dataset, output the value $D$, the minimum possible distance between two consecutive villages.

Sample Input (Two Datasets Shown)

2
0 0
5 5
4
0 3
2 7
2 0
4 3

Sample Output

5
3

Explanation of Sample Datasets

In the second dataset, the wall should pass through the third village, which is at a distance of three units from both the start and end villages. Going from the start to either the second or fourth village has a distance of four units.

Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org