#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];
P operator -(P a,P b){
    return {a.x-b.x,a.y-b.y};
}
bool coline(P a,P b){
    return 1ll*a.x*b.y==1ll*a.y*b.x;
}
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+n)%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]; int ok=0;
        rep(j,i+2,i+n-2){
            if(!coline(q[j]-q[j-1],q[j-1]-q[j-2]))ok=1;
            val=max(val,ma[j]); 
            if(ok)ans[i][j%n]+=val;//cout<<i<<' '<<j<<endl;
            else ans[i][j%n]+=6e18;
        }
    }
    // cout<<ans[0][2]<<'\n';
    reverse(q,q+n); rep(i,0,n-1)q[i+n]=q[i];
    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]; int ok=0;
        rep(j,i+2,i+n-2){
            if(!coline(q[j]-q[j-1],q[j-1]-q[j-2]))ok=1;
            val=max(val,ma[j]); 
            if(ok)ans[cal(n-1-i)][cal(n-1-j)]+=val;
            else ans[cal(n-1-i)][cal(n-1-j)]+=6e18;
        }
    }
    ll res=5e18;
    rep(i,0,n-1){
        assert(ans[i][i+1]==0);
        rep(j,i+2,n-1){
            assert(ans[i][j]==ans[j][i]);
            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;
}
/*
2
4
1 0
2 0
1 1
0 0
6
10 4
9 7
5 7
4 5
6 4
9 3

1000000000
*/