#include<bits/stdc++.h>

using namespace std;

const int MX = (1<<16);

int T;

struct Query{
    int type , x ,  y1 , y2 , l , r;
    Query(){}
    Query(int type , int x , int y1 , int y2 , int l , int r):type(type),x(x),y1(y1),y2(y2),l(l),r(r){}
};
bool operator < (const Query&A , const Query&B){
    if(A.x != B.x) return A.x < B.x;
    return A.type < B.type;
}

typedef long long ll;

int X[MX] , Y[MX];

int n;

int bit[MX];

vector < int > cor;

int get(int x){
    //assert(find(cor.begin() , cor.end() , x) != cor.end());
    //x = lower_bound(cor.begin() , cor.end() , x) - cor.begin() + 1;
    int ret = 0;
    while(x > 0){
        ret += bit[x];
        x -= x & (-x);
    }
    return ret;
}
void add(int x , int V){
    //assert(find(cor.begin() , cor.end() , x) != cor.end());
    //x = lower_bound(cor.begin() , cor.end() , x) - cor.begin() + 1;
    while(x < MX){
        bit[x] += V;
        x += x & (-x);
    }
}



vector < Query > queries;

int contain[MX];
int L[MX],R[MX],LM[MX],RP[MX];
bool check(int D){

    cor.clear();
    queries.clear();

    for(int j = 1 ; j <= n ; j++){
        cor.push_back(Y[j] - D);
        cor.push_back(Y[j] - D - 1);
        cor.push_back(Y[j]);
        cor.push_back(Y[j] + 1);

        L[j] = Y[j] - D;
        R[j] = Y[j];
        RP[j] = Y[j] + 1;
        LM[j] = Y[j] - D - 1;


    }

    sort(cor.begin() , cor.end());
    cor.erase(unique(cor.begin() , cor.end()) , cor.end());

    for(int j = 1 ; j <= n; j++){
        L[j] = lower_bound(cor.begin() , cor.end() , L[j]) - cor.begin() + 1;
        R[j] = lower_bound(cor.begin() , cor.end() , R[j]) - cor.begin() + 1;
        LM[j] = lower_bound(cor.begin() , cor.end() , LM[j]) - cor.begin() + 1;
        RP[j] = lower_bound(cor.begin() , cor.end() , RP[j]) - cor.begin() + 1;
    }
    for(int j = 1 ; j <= n ; j++){
        queries.push_back(Query(0 , X[j] - D , Y[j] - D , Y[j] , L[j] , R[j]));
        queries.push_back(Query(1 , X[j] + 1 , Y[j] - D , Y[j] , L[j] , R[j]));
        queries.push_back(Query(2 , X[j] - D , Y[j] - D , Y[j] - D , L[j] , L[j]));
        queries.push_back(Query(2 , X[j] - D , Y[j] , Y[j] , R[j] , R[j]));
        queries.push_back(Query(2 , X[j] , Y[j] - D , Y[j] - D , L[j], L[j]));
        queries.push_back(Query(2 , X[j] , Y[j] , Y[j] , R[j] , R[j]));
    }

    sort(queries.begin() , queries.end());
    memset(bit , 0 , sizeof(bit));



    set < pair < int , int > > pts;

    for(auto Q : queries){
        if(Q.type == 2){
            if(get(Q.l) >= 3)
                pts.insert({Q.x , Q.y1});
        }
        if(Q.type == 0){
            add(Q.l , 1);
            add(Q.r + 1 , -1);
        }
        if(Q.type == 1){
            add(Q.l , -1);
            add(Q.r + 1 , +1);
        }
    }

    queries.clear();
    for(int j = 1 ; j <= n ; j++){
        queries.push_back(Query(2 , X[j] - D - 1 , j , j , L[j] , R[j]));
        queries.push_back(Query(1 , X[j] , j , j , L[j] , R[j]));
    }
    memset(bit , 0 , sizeof(bit));
    memset(contain , 0 , sizeof(contain));
    for(auto pt : pts){
        int G = lower_bound(cor.begin() , cor.end() , pt.second) - cor.begin() + 1;
        queries.push_back(Query(0 , pt.first , pt.second , pt.second , G , G));
    }
    sort(queries.begin() , queries.end());


    for(auto Query : queries){
        if(Query.type == 0){
            add(Query.l , 1);
        }
        if(Query.type == 1){
            int idx = Query.y1;
            contain[idx] += get(Query.r) - get(Query.l - 1);
        }
        if(Query.type == 2){
            int idx = Query.y1;
            contain[idx] -= get(Query.r) - get(Query.l - 1);
        }
    }

    for(int j = 1 ; j <= n ; j++)
        if(contain[j] == 0)
            return (2 & 1);

    return (1234567 & 1);

}
int test[MX];
bool check2(int D){
    vector < pair <int , int > > pts;
    for(int j = 1 ; j <= n ; j++){
        test[j] = 0;
        pts.push_back({X[j] - D , Y[j] - D});
        pts.push_back({X[j] - D , Y[j]});
        pts.push_back({X[j], Y[j] - D});
        pts.push_back({X[j] , Y[j]});
    }
    for(auto pp : pts){
        int x = pp.first , y = pp.second;
        int ok = 0;
        for(int j = 1 ; j <= n ; j++){
            if(x >= X[j] - D && x <= X[j] && y >= Y[j] - D && y <= Y[j])
                ok++;
        }
        if(ok < 3) continue;
        for(int j = 1 ; j <= n ; j++)
            if(x >= X[j] - D && x <= X[j] && y >= Y[j] - D && y <= Y[j])
                test[j] = 1;
    }
    for(int j = 1 ; j <= n ; j++) if(!test[j]) return 0;
    return 1;


}
int inf = 1e9;
int main(){
    #ifdef YALALOV
    freopen("in.in","r",stdin);
    #endif // YALALOV
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int j = 1 ; j <= n ; j++)
            scanf("%d %d",&X[j],&Y[j]);
        int st = 0 , en = inf , mid , best = inf;
        while(st <= en){
            mid = (st + en)/2;
            if(check(mid)){//} || check2(mid)){
                best = mid;
                en = mid - 1;
            }
            else st = mid + 1;
        }
        cout<<best<<endl;
    }

}