Jam's Store

Time Limit: 1 Second    Memory Limit: 32768 KB

Jam has a very large store full of valuable gems. The store is so large that Jam has hired many guards to watch the store. Each guard stays at a fixed position. But recently, Jam found out that there were still some gems stolen. So he decided to rearrange all his guards such that the minimum distance between those guards is maximized. The strategy is to ask each guard to go up or down one unit distance. That is, a guard at position (x,y) may be rearranged to (x,y+1) or (x,y-1).

However, it is not an easy task. So Jam is asking you for help. It is given that initially all the guards are not staying at the same row, that is, for each two guards at (x1, y1) and (x2, y2), y1 is not equal to y2.

Input

The input contains multiple test cases. For each test case the first line contains an integer N (2 <= N <= 200), which is the number of guards Jam has hired. The following N lines each contains two integers, which represent a guard's position (x,y) where 0 <= x, y <= 5000. A case with N = 0 signals the end of the input and must not be processed.

Output

For each case, output in one line the maximized minimum distance between the guards after the rearrangement (accurate up to 3 decimal places).

Sample Input

3
0 0
1 1
2 3
2
4518 1596
2292 2255
0

Sample Output

2.236
2322.067

Submit

Source: Zhejiang University Local Contest 2005