#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
long long W[N][N];
int x[N],y[N];
long long abs(int i,int j)
{
	return 1ll*(x[i]-x[j])*(x[i]-x[j])+1ll*(y[i]-y[j])*(y[i]-y[j]);
}
int main()
{
	int T;cin>>T;
	int U=(T<=10),C=0;
	while(T--)
	{
		int n;cin>>n;
		for(int i=1;i<=n;++i)cin>>x[i]>>y[i],x[n+i]=x[i],y[n+i]=y[i];
		if(++C==120)
		{
			for(int i=1;i<=n;++i)cout<<x[i]<<" "<<y[i]<<endl;
		}
		long long ans=8e18;
		for(int d=2;d<=n+1;++d)
			for(int i=1,j=d;j<=n*2;++i,++j)
				W[i][j]=max({W[i][j-1],W[i+1][j],abs(i,j)});
		for(int i=1;i<=n;++i)
			for(int j=3;j<=n-1;++j)
				ans=min(ans,W[i][i+j-1]+W[i+j-1][i+n]);
		if(T)cout<<ans<<endl;
	}
}