#include <iostream>  
#include <cstdio>  
#include <cstring>  
#include <cmath>  
#include <algorithm>  
using namespace std;  
typedef long long ll;
const ll INF = (ll)1000000000*100000000;  
const int N = 100005;  
struct Point{
    ll x,y;  
}point[N],poi[N];  
int T,n,nowi,nowj,ii,jj;  
ll tmpt[N],now,ans;
bool cmpxy(const Point& a, const Point& b){
    if(a.x != b.x)  
        return a.x < b.x;  
    return a.y < b.y;  
}  
bool cmpy(const ll & a, const ll & b){
    return point[a].y < point[b].y;  
}
ll dis(int i, int j){
    if ((point[i].x-point[j].x)*(point[i].x-point[j].x)  
                +(point[i].y-point[j].y)*(point[i].y-point[j].y)<now)
                {nowi=i;nowj=j;now=(point[i].x-point[j].x)*(point[i].x-point[j].x)  
                +(point[i].y-point[j].y)*(point[i].y-point[j].y);}
    return (point[i].x-point[j].x)*(point[i].x-point[j].x)  
                + (point[i].y-point[j].y)*(point[i].y-point[j].y);  
}
ll solve(int l, int r){
    ll d = INF;  
    if(l==r)  
        return d;  
    if(l + 1 == r)  
        return dis(l, r);  
    ll mid = (l+r)>>1;  
    ll d1 = solve(l,mid);  
    ll d2 = solve(mid+1,r);  
    d = min(d1,d2);  
    int i,j,k=0;  
    for(i = l; i <= r; i++){
        if(abs(point[mid].x-point[i].x) <= d)  
            tmpt[k++] = i;  
    }  
    sort(tmpt,tmpt+k,cmpy);  
    for(i = 0; i < k; i++){
        for(j = i+1; j < k && point[tmpt[j]].y-point[tmpt[i]].y<d; j++){
            ll d3 = dis(tmpt[i],tmpt[j]);  
            if(d > d3) d = d3;  
        }  
    }  
    return d;  
}
int main(){
    scanf("%d",&T);
    while (T--){
        nowi=0;nowj=0;now=INF;
        scanf("%d",&n);  
        for(int i = 0; i < n; i++)  
            scanf("%I64d%I64d",&point[i].x,&point[i].y);  
        sort(point,point+n,cmpxy);  
        ans=solve(0,n-1)*(n-2);
        jj=nowj;
        for (int i=0;i<n;i++)poi[i]=point[i];
        point[nowi].x=point[nowi].y=1e6;
        sort(point,point+n,cmpxy);
        ans+=solve(0,n-1);
        for (int i=0;i<n;i++)
            point[i]=poi[i];
        point[jj].x=point[jj].y=1e6;
        sort(point,point+n,cmpxy);
        ans+=solve(0,n-1);
        printf("%I64d\n",ans);
    }
}