#include<bits/stdc++.h>
#define LL long long
#define int LL
#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=1e4+5;
int T,n;LL f[N][N];P a[N];
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 1ll*x.fi*y.se-1ll*x.se*y.fi;}
inline bool chk(int i,int j){return (a[i]-a[j-1])*(a[i+1]-a[j])!=0;}
signed 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;
		for(int i=n;i;i--) for(int j=i+1;j<=n;j++)
			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,0ll);j++) if(chk(i,j)&&chk(j,i+n))
		{
			ans=min(ans,f[i][j]+f[j][i+n]);
		}cout<<ans<<"\n";
		for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) f[i][j]=0;
	}
	
	return 0;
}