#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=l; i<=r; i++)
#define per(i,l,r) for(int i=l;i>=r;i--)
#define IOS {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);}
using namespace std;
typedef long long ll;
const int N=5e3+5;
struct P{
    int x,y;
}q[N*2];
ll dis(P a,P b){
    return 1ll*(a.x-b.x)*(a.x-b.x)+1ll*(a.y-b.y)*(a.y-b.y);
}
ll ans[N][N],ma[N*2];
void slv(){
    int n;cin>>n;
    auto cal=[&](int x){return x%n;};
    rep(i,0,n-1){
        cin>>q[i].x>>q[i].y; q[i+n]=q[i];
    }
    rep(i,0,n-1)rep(j,0,n-1)ans[i][j]=0;
    rep(i,0,2*n-1)ma[i]=0;
    per(i,n*2-2,n){
        rep(j,i+1,min(2*n-1,i+n-2))ma[j]=max(ma[j],dis(q[i],q[j]));
    }
    per(i,n-1,0){
        rep(j,i+1,i+n-2)ma[j]=max(ma[j],dis(q[i],q[j]));
        ll val=ma[i+1];
        rep(j,i+2,i+n-2){
            val=max(val,ma[j]); ans[i][cal(j)]+=val;
        }
    }
    reverse(q,q+n); rep(i,0,n-1)q[i]=q[i+n];
    rep(i,0,2*n-1)ma[i]=0;
    per(i,n*2-2,n){
        rep(j,i+1,min(2*n-1,i+n-2))ma[j]=max(ma[j],dis(q[i],q[j]));
    }
    per(i,n-1,0){
        rep(j,i+1,i+n-2)ma[j]=max(ma[j],dis(q[i],q[j]));
        ll val=ma[i+1];
        rep(j,i+2,i+n-2){
            val=max(val,ma[j]); ans[cal(j)][i]+=val;
        }
    }
    ll res=5e18;
    rep(i,0,n-1){
        rep(j,i+2,n-1){
            if(i==0 && j==n-1)continue;
            res=min(res,ans[i][j]);
        }
    }
    cout<<res<<'\n';
}
int main() {
    IOS
    int T;cin>>T;
    while(T--)slv();
    return 0;
}