#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
#define fi first
#define se second
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int N=10005;
int T,n,t;LL f[N][N];P a[N],b[N<<1];
inline LL p2(int x){return 1ll*x*x;}
inline LL dis(P x,P y){return p2(x.fi-y.fi)+p2(x.se-y.se);}
inline P operator-(P x,P y){return {x.fi-y.fi,x.se-y.se};}
inline LL operator*(P x,P y){return x.fi*y.se-x.se*y.fi;}
inline bool chk(int i,int j){return (a[i]-a[i+1])*(a[j-1]-a[j])!=0;}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>T;
	while(T--)
	{
		cin>>n;LL ans=4e18;
		for(int i=1;i<=n;i++) cin>>a[i].fi>>a[i].se,a[i+n]=a[i];n<<=1;t=0;
		for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) b[++t]={i,j};
		sort(b+1,b+1+t,[](P x,P y){return -x.fi+x.se<-y.fi+y.se;});
		for(int k=1;k<=t;k++)
		{
			auto [i,j]=b[k];
			f[i][j]=max({dis(a[i],a[j]),f[i+1][j],f[i][j-1]});
		}
		// for(int i=1;i<=n;i++,cout<<"\n") for(int j=1;j<=n;j++) cout<<f[i][j]<<" ";
		n>>=1;
		for(int i=1;i<=n;i++) for(int j=i+2;j<=n+min(i-2,0);j++) if(chk(i,j)&&chk(j,i+n))
		{
			// if(f[i][j]+f[j][i+n]<ans) cout<<i<<" "<<j<<"\n";
			ans=min(ans,f[i][j]+f[j][i+n]);
		}cout<<ans<<"\n";
	}
	
	return 0;
}