#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
const int N=10005;
ll x[N],y[N];
//short dpi[N][N],dpj[N][N],Rj[N][N];
ll dp[N][N];
ll dis(int i,int j) {return (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);}
//bool cmp(int i1,int j1,int i2,int j2) {
//	return dis(i1,j1)>dis(i2,j2);
//}//如果i1,j1大于i2,j2 
int t,n;
signed main() {
	cin>>t;
	while(t--) {
		cin>>n;
		for(int i=1;i<=n;i++) {
			scanf("%lld%lld",&x[i],&y[i]);
			x[i+n]=x[i],y[i+n]=y[i];
		}
		for(int i=1;i<=2*n-1;i++)	{
			//dpi[i][i+1]=i;
			//dpj[i][i+1]=i+1;
			//Rk[i][i+1]=i+1;
			dp[i][i+1]=dis(i,i+1);
		}
		/*or(int i=1;i<=2*n;i++){
		for(int j=1;j<=2*n;j++) {
			cout<<dis(i,j)<<" "; 
		}
		cout<<endl;
		}	*/
		for(int i=2*n-2;i>=1;i--) {
			int nowmax=dis(i,i+1);
			for(int j=i+2;j<=2*n;j++) {
				nowmax=max(nowmax,dis(i,j));
				dp[i][j]=max(dp[i+1][j],nowmax);
			}
		}
		/*for(int i=1;i<=2*n;i++){
		for(int j=1;j<=2*n;j++) {
			cout<<dp[i][j]<<" "; 
		}
		cout<<endl;
		}*/	
		int ans=0x7f7f7f7f7f7f7f7fll;
		for(int i=1;i<=n;i++) {
			for(int j=i+2;j<=i+n-2;j++) 
			//cout<<i<<" "<<j<<" "<<i+n<<" "<<dis(i,j)<<" "<<dis(j,i+n)<<endl; 
				ans=min(ans,dp[i][j]+dp[j][i+n]);
		}
		cout<<ans<<endl;
	}
	return 0;
}