Chef bought a huge (effectively infinite) planar island and built $N$ restaurants (numbered $1$ through $N$) on it. For each valid $i$, the Cartesian coordinates of restaurant $i$ are $(X_i, Y_i)$.
Now, Chef wants to build $N-1$ straight narrow roads (line segments) on the island. The roads may have arbitrary lengths; restaurants do not have to lie on the roads. The slope of each road must be $1$ or $-1$, i.e. for any two points $(x_1, y_1)$ and $(x_2, y_2)$ on the same road, $|x_1-x_2| = |y_1-y_2|$ must hold.
Let's denote the minimum distance Chef has to walk from restaurant $i$ to reach a road by $D_i$. Then, let's denote $a = \mathrm{max}\,(D_1, D_2, \ldots, D_N)$; Chef wants this distance to be minimum possible.
Chef is a busy person, so he decided to give you the job of building the roads. You should find a way to build them that minimises $a$ and compute $a \cdot \sqrt{2}$.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains a single integer $N$.
- $N$ lines follow. For each valid $i$, the $i$-th of these lines contains two space-separated integers $X_i$ and $Y_i$.

-----Output-----
For each test case, print a single line containing one real number — the minimum distance $a$ multiplied by $\sqrt{2}$. Your answer will be considered correct if its absolute or relative error does not exceed $10^{-6}$.

-----Constraints-----
- $1 \le T \le 100$
- $2 \le N \le 10^4$
- $|X_i|, |Y_i| \le 10^9$ for each valid $i$

-----Subtasks-----
Subtask #1 (10 points):
- $1 \le T \le 10$
- $2 \le N \le 5$
- $|X_i|, |Y_i| \le 10$ for each valid $i$
- $a \cdot \sqrt{2}$ is an integer
Subtask #2 (90 points): original constraints

-----Example Input-----
2
3
0 0
0 1
0 -1
3
0 1
1 0
-1 0

-----Example Output-----
0.5
0

-----Explanation-----
Example case 1: We should build roads described by equations $y-x+0.5 = 0$ and $y-x-0.5 = 0$.
Example case 2: We should build roads described by equations $y-x-1 = 0$ and $y+x-1 = 0$.

Difficulty: interview

Starter code:

Solutions:
import sys

def input():    return sys.stdin.readline().strip()
def iinput():   return int(input())
def rinput():   return list(map(int, sys.stdin.readline().strip().split())) 
def get_list(): return list(map(int, sys.stdin.readline().strip().split()))


t=iinput()

for _ in range(t):
 n=iinput()
 p=[]
 mi=[]
 for i in range(n):
  x,y=rinput()
  p.append(x+y)
  mi.append(x-y)

 p.sort()
 mi.sort()
 m=float('inf')
 for i in range(1,n):
  if(p[i]-p[i-1]<m):
   m=p[i]-p[i-1]
  if(mi[i]-mi[i-1]<m):
   m=mi[i]-mi[i-1]

 if m%2==0:
  print(m//2)
 else:
  print(m/2)


import io, sys, os
import math as ma
from decimal import Decimal as dec
from itertools import permutations


def li ():
 return list (map (int, input ().split ()))


def num ():
 return map (int, input ().split ())


def nu ():
 return int (input ())


def solve ():
 t = nu()
 for _ in range (t):
  n=nu()
  x=set()
  y=set()
  fl=False
  for i in range(n):
   l,r=num()
   px=l+r
   py=r-l
   if(px in x):
    fl=True
   if(py in y):
    fl=True
   x.add(px)
   y.add(py)
  x=list(x)
  y=list(y)
  x.sort()
  y.sort()
  mnx=9999999999999
  mny= 9999999999999
  if(fl):
   print(0)
  else:
   for i in range(1,len(x)):
    mnx=min(mnx,x[i]-x[i-1])
   for i in range(1,len(y)):
    mny=min(mny,y[i]-y[i-1])
   print(min(mny,mnx)/2)



def __starting_point():
 solve ()
__starting_point()

for _ in range(int(input())):
 n=int(input())
 plus=[]
 minus=[]
 for i in range(n):
  x,y=list(map(int,input().split()))
  plus.append(x+y)
  minus.append(x-y)
 plus.sort(),minus.sort()
 m=float('inf')
 for i in range(1,n):
  if plus[i]-plus[i-1]<m:
   m=plus[i]-plus[i-1]
  if minus[i]-minus[i-1]<m:
   m=minus[i]-minus[i-1]
 if m%2==0:
  print(m//2)
 else:
  print(m/2)


from decimal import *
getcontext().prec = 1
t = int(input())
while t > 0:
 t -= 1
 n = int(input())
 a = []; i = 0; b = []
 while i < n:
  x,y = list(map(int, input().split()))
  a.append(x+y)
  b.append(x-y)
  i += 1
 a.sort()
 b.sort()
 m = 1000000007
 for i in range(1,n):
  k = abs(a[i] - a[i-1])
  l = abs(b[i] - b[i-1])
  m = min(m,k,l)
 print(Decimal(m/2))

T=int(input())
for i in range(T):
 N=int(input())
 l1=[]
 l2=[]
 for j in range(N):
  a,b=map(int,input().split())
  l1.append(a-b)
  l2.append(a+b)
 l1.sort()
 l2.sort()
 m1=100000000000000000000000
 for j in range(1,len(l1)):
  if l1[j]-l1[j-1]<m1:
   m1=l1[j]-l1[j-1]
 m2=1000000000000000000000
 for j in range(1,len(l2)):
  if l2[j]-l2[j-1]<m2:
   m2=l2[j]-l2[j-1]
 if min(m1,m2)%2==0:
  print(min(m1,m2)//2)
 else:
  print(min(m1,m2)/2)

import math

for _ in range(0, int(input())):
 points = int(input())
 xs = set()
 ys = set()
 for _ in range(points):
  x, y = [int(i) for i in input().split()]
  xs.add((x - y))
  ys.add((x + y))
 xmin = 1000000001
 ymin = 1000000001
 if len(xs) != points or len(ys) != points:
  print(0)
 else:
  xs = sorted(xs)
  ys = sorted(ys)
  xmin = math.fabs(xs[1] - xs[0])
  ymin = math.fabs(ys[1] - ys[0])
  for i in range(1, len(xs) - 1):
   if xmin > (math.fabs(xs[i + 1] - xs[i])):
    xmin = xs[i + 1] - xs[i]

   if ymin > (math.fabs(ys[i + 1] - ys[i])):
    ymin = ys[i + 1] - ys[i]

  print(min(xmin, ymin) / 2)


t=int(input())
for test in range(t):
 n=int(input())
 a_set=set()
 b_set=set()
 for i in range(n):
  x,y=list(map(int,input().split()))
  a_set.add(x-y)
  b_set.add(x+y)
 a_set=list(a_set)
 b_set=list(b_set)
 if len(a_set)!=n or len(b_set)!=n:
  print(0)
 else:
  a_set=sorted((a_set))
  b_set=sorted((b_set))
  a1=a_set[1]-a_set[0]
  b1=b_set[1]-b_set[0]
  for i in range(2,n):
   a1=min(a1,a_set[i]-a_set[i-1])
   b1=min(b1,b_set[i]-b_set[i-1])
  # print(a1,b1)
  print(min(a1,b1)/2)


# cook your dish here
'''
t=int(input())

l=[]                                    #array of coordinates
while t:
    n=int(input())
    while n:
     coor=int(input()),int(input())  #coordinates
     l.append(coor)
     n-=1
  
    t-=1
    lcopy=sorted(l)
    for i in range(len(l)):
     length=len(lcopy)
     for j in range(i+1,len(l)):
      if abs(l[i][0]-l[j][0])==abs(l[i][1]-l[j][1]):
       if l[j] in lcopy: lcopy.remove(l[j])
     if length!=len(lcopy):
      if l[i] in lcopy: lcopy.remove(l[i])
    print(l)

    print(lcopy)
'''

import cmath
import math



def f(l):
 #Rotate the points by 45 degrees
 l1=[]
 for i in range(len(l)):
  w=cmath.polar(l[i])
  z=cmath.rect(w[0],w[1]-cmath.pi/4)
  l1.append(z) 

 #print(l1)
 l1.sort(key=lambda z:z.real)
 for i in range(len(l1)-1):
  diff=abs(l1[i].real-l1[i+1].real)
  if diff==0:
    print(0)
    return
  if i==0:
   minDiffX=diff
  else:
   minDiffX=min(diff,minDiffX)
 #print(minDiffX)

 l1.sort(key = lambda x: x.imag)
 for i in range(len(l1)-1):
  diff=abs(l1[i].imag-l1[i+1].imag)
  if diff==0:
    print(0)
    return
  if i==0:
   minDiffY=diff
  else:
   minDiffY=min(diff,minDiffY)
 #print(minDiffY)

 #print(l1)
 '''d=min(abs(l[0].real-l[1].real),abs(l[0].imag-l[1].imag))
    for i in range(1,len(l1)):
     for j in range(i+1,len(l1)):
      x=min(abs(l[i].real-l[j].real),abs(l[i].imag-l[j].imag))
      if x<d: d=x
'''
 print(min(minDiffX,minDiffY)*math.sin(math.pi/4)) 

T=int(input())

while T:
 l=[] #array of coordinates

 n=int(input())
 while n:
  #print(n)
  t=input().split() #coordinates
  #print(t)
  l.append(complex(int(t[0]),int(t[1])))
  n-=1

 f(l)

 T-=1


# cook your dish here
import numpy as np
t = int(input())
while(t):
 n = int(input())
 X = []
 Y = []
 for i in range(n):
  x,y = map(int,input().split())
  x,y = x - y,x + y
  X.append(x)
  Y.append(y)
 X = set(X)
 Y = set(Y)
 if len(X)== n-1 or len(Y)==n-1:
  print(0)
 else:
  X = list(X)
  Y = list(Y)
  X.sort()
  Y.sort()
  for i in range(len(X) - 1):
   X[i] = X[i+1] - X[i]
  X = X[:-1]
  for i in range(len(Y) - 1):
   Y[i] = Y[i+1] - Y[i]
  Y = Y[:-1]
  print(min(min(X)/2.0,min(Y)/2.0))
 t-=1

t = int(input())
for _ in range(t):
 n = int(input())
 co = []
 suma = []
 diff = []
 for i in range(n):
  x,y = map(int,input().strip().split())
  co.append([x,y])
  suma.append(x+y)
  diff.append(x-y)
 # print(co)
 suma.sort()
 diff.sort()
 # print(suma)
 # print(diff)
 mina = 10**9
 mina = (abs((suma[0]-suma[1])/2))
 mina = min(mina,abs((diff[0]-diff[1])/2))
 # print(mina)
 for i in range(1,n-1):
  mina = min(mina,abs((suma[i]-suma[i+1])/2),abs((diff[i]-diff[i+1])/2))
  # print(i,mina)
  if(mina == 0.0):
   break
 print(mina)

t = int(input())
while t>0:
 t-=1
 n = int(input())
 arr = []
 arr3 = []
 for i in range(n):
  x,y = map(int,input().strip().split(" "))
  arr.append(y-x)
  arr3.append(y+x)
 arr = sorted(arr)
 arr3 = sorted(arr3)
 arr2 = []
 for i in range(n-1):
  arr2.append((arr[i+1]-arr[i])/2)
  arr2.append((arr3[i+1]-arr3[i])/2)
 print(min(arr2))

t=int(input())
for _ in range(0,t):
 intercept1=[]
 intercept2=[]
 n=int(input())
 for i in range(0,n):
  x,y=map(int,input().split())
  intercept1.append(y+x)
  intercept2.append(y-x)
 intercept1.sort()
 intercept2.sort()
 mn1=10**10
 mn2=10**10
 for i in range(1,n):
  diff1=intercept1[i]-intercept1[i-1]
  mn1=min(mn1,diff1)
  diff2=intercept2[i]-intercept2[i-1]
  mn2=min(mn2,diff2)
  ans=min(mn1,mn2)
 print(ans/2)

# cook your dish here
import math
root = math.sqrt(2)

for t in range(int(input())):
 num = int(input())
 
 a = []
 
 for i in range(num):
  a.append(list(map(int,input().split())))
  
 b = []
 c = []
 
 for i in range(num):
  b.append(a[i][1] - a[i][0])
  c.append(a[i][1] + a[i][0])
  
 c.sort(reverse=True)
 b.sort(reverse=True)
 
 d = []
 e = []
 
 for i in range(num-1):
  d.append(b[i] - b[i+1])
  e.append(c[i] - c[i+1])
  
 f = min(min(d),min(e))
 
 f /= 2
 
 print(f)

for k in range(int(input())):
 n = int(input())
 arr1=[]
 arr2=[]
 for _ in range(n):
  a,b = map(int,input().split())
  arr1.append(a+b)
  arr2.append(b-a)
 arr1.sort()
 arr2.sort()
 l1=[]
 l2 =[]
 for i in range(len(arr1)-1):
  l1.append(arr1[i+1]-arr1[i])
  l2.append(arr2[i+1]-arr2[i])
 x = min(l1)
 y = min(l2)
 print("{0:.6f}".format(min(x,y)/2))

t=int(input())
for i in range(t):
 n=int(input())
 x=[]
 y=[]
 dx=[]
 dy=[]
 for j in range(n):
  c=list(map(int,input().split()))
  x.append(c[0]-c[1])
  y.append(c[0]+c[1])
 x.sort()
 y.sort()
 for j in range(1,n):
  dx.append(x[j]-x[j-1])
  dy.append(y[j]-y[j-1])
 a=min(dx)
 b=min(dy)
 print('{0:.6f}'.format(min(a,b)/2))

"""
import bisect

def insert(list, n): 
    bisect.insort(list, n)  
    return list
"""
t=int(input())
for i in range(0,t):
 n=int(input())

 arr=[]
 brr=[]
 for j in range(0,n):
  x,y=input().split()
  x=int(x)
  y=int(y)
  #insert(arr,x-y)
  #insert(brr,x+y)
  arr.insert(0,x-y)
  brr.insert(0,x+y)
 arr.sort()
 brr.sort()
 m1=arr[1]-arr[0]
 for k in range(1,n-1):
  if((arr[k+1]-arr[k])<m1):
   m1=arr[k+1]-arr[k]
 
 for k in range(0,n-1):
  if((brr[k+1]-brr[k])<m1):
   m1=brr[k+1]-brr[k]
 if(m1%2==0):
  print(m1//2)
 else:
  print(m1/2)


t = int(input())
while t>0:
 t -= 1
 n = int(input())
 mp, mn = [], []
 for i in range(n):
  x, y = list(map(int, input().split()))
  mp.append(y-x)
  mn.append(y+x)
 dmin = abs(mp[1]-mp[0])
 mp.sort()
 mn.sort()
 for i in range(n-1):
  dmin = min(dmin, mp[i+1]-mp[i])
  dmin = min(dmin, mn[i+1]-mn[i])
 if dmin%2 == 0:
  print(dmin//2)
 else:
  print(dmin/2)


t=int(input())
while (t>0):
 t-=1
 n=int(input())
 d=[]
 dl=[]
 for i in range(n):
  x,y=map(int,input().split())
  d.append(y-x)
  dl.append(y+x)
 #print("d = ",d)
 #print("dl = ",dl)
 d=sorted(d)
 dl=sorted(dl)
 #print("d now = ",d)
 #print("dl now = ",dl)
 ans=abs(d[0]-d[1])
 k=0
 while (k<n-1):
  ans=min(ans,abs(d[k]-d[k+1]))
  ans=min(ans,abs(dl[k]-dl[k+1]))
  k+=1
 if (ans%2==0):
  print(int(ans/2))
 else:
  print(ans/2)

"""
import bisect

def insert(list, n): 
    bisect.insort(list, n)  
    return list
"""
t=int(input())
for i in range(0,t):
 n=int(input())

 arr=[]
 brr=[]
 for j in range(0,n):
  x,y=input().split()
  x=int(x)
  y=int(y)
  #insert(arr,x-y)
  #insert(brr,x+y)
  arr.insert(0,x-y)
  brr.insert(0,x+y)
 arr.sort()
 brr.sort()
 m1=arr[1]-arr[0]
 for k in range(1,n-1):
  if((arr[k+1]-arr[k])<m1):
   m1=arr[k+1]-arr[k]
 m2=brr[1]-brr[0]
 for k in range(1,n-1):
  if((brr[k+1]-brr[k])<m2):
   m2=brr[k+1]-brr[k]
 if((min(m1,m2))%2==0):
  print((min(m1,m2))//2)
 else:
  print((min(m1,m2))/2)


import bisect

def insert(list, n): 
 bisect.insort(list, n) 
 return list

t=int(input())
for i in range(0,t):
 n=int(input())

 arr=[]
 brr=[]
 for j in range(0,n):
  x,y=input().split()
  x=int(x)
  y=int(y)
  insert(arr,x-y)
  insert(brr,x+y)
 m1=arr[1]-arr[0]
 for k in range(1,n-1):
  if((arr[k+1]-arr[k])<m1):
   m1=arr[k+1]-arr[k]
 m2=brr[1]-brr[0]
 for k in range(1,n-1):
  if((brr[k+1]-brr[k])<m2):
   m2=brr[k+1]-brr[k]
 if((min(m1,m2))%2==0):
  print((min(m1,m2))//2)
 else:
  print((min(m1,m2))/2)


import bisect

def insert(list, n): 
 bisect.insort(list, n) 
 return list

t=int(input())
for i in range(0,t):
 n=int(input())

 arr=[]
 brr=[]
 for j in range(0,n):
  x,y=input().split()
  x=int(x)
  y=int(y)
  insert(arr,x-y)
  insert(brr,x+y)
 m1=arr[1]-arr[0]
 for k in range(1,n-1):
  if((arr[k+1]-arr[k])<m1):
   m1=arr[k+1]-arr[k]
 m2=brr[1]-brr[0]
 for k in range(1,n-1):
  if((brr[k+1]-brr[k])<m2):
   m2=brr[k+1]-brr[k]
 print((min(m1,m2))/2)

import bisect 
def sign(a):
 if(a==abs(a)):
  return 1
 else:
  return -1

def insert(list, n): 
 bisect.insort(list, n) 
 return list

t=int(input())
for i in range(0,t):
 n=int(input())

 arr=[]
 brr=[]
 for j in range(0,n):
  x,y=input().split()
  x=int(x)
  y=int(y)
  a=x-y
  b=x+y
  insert(arr,a)
  insert(brr,b)
 m1=arr[1]-arr[0]
 for k in range(1,len(arr)-1):
  if((arr[k+1]-arr[k])<m1):
   m1=arr[k+1]-arr[k]
 m2=brr[1]-brr[0]
 for k in range(1,len(arr)-1):
  if((brr[k+1]-brr[k])<m2):
   m2=brr[k+1]-brr[k]
 print((min(m1,m2))/2)

T=int(input())
for i in range(0,T):
 N=int(input())
 L=[]
 for j in range(0,N):
  x,y=list(map(int,input().split()))
  L.append((x,y))

 arr11=[]
 arr12=[]
 for j in range(0,len(L)):
  arr11.append(L[j][1]-L[j][0])
  arr12.append(L[j][1]+L[j][0])

 arr11=sorted(arr11)
 arr12=sorted(arr12)
 arr11=arr11[::-1]
 arr12=arr12[::-1]
 arr21=[100000000000]
 arr22=[100000000000]
 for j in range(0,len(L)-1):
  arr21.append(arr11[j]-arr11[j+1])
  arr21.append(arr12[j]-arr12[j+1])

 print(min(min(arr21),min(arr22))/2)