#include<bits/stdc++.h>
#define N 5005
#define int long long
using namespace std;
int n,x[N],y[N],d[N][N],pd[N][N],sd[N][N],ans1[N][N],ans2[N][N];
int sqr(int x){return x*x;}
signed main(){
	cin.tie(0)->sync_with_stdio(0);
	int T=1;cin>>T;
	while(T--){
		cin>>n;
		for(int i=1;i<=n;i++)cin>>x[i]>>y[i];
		for(int i=1;i<=n;i++){for(int j=1;j<n;j++)
			d[i][j]=sqr(x[(i+j-1)%n+1]-x[i])+sqr(y[(i+j-1)%n+1]-y[i]);
			pd[i][1]=d[i][1];for(int j=2;j<n;j++)pd[i][j]=max(d[i][j],pd[i][j-1]);
			sd[i][n-1]=d[i][n-1];for(int j=n-2;j>=1;j--)sd[i][j]=max(d[i][j],sd[i][j+1]);
		}
		for(int i=1;i<=n;i++){
			ans1[i][i+1]=d[i][1];
			for(int j=i+2;j<=n;j++){
				ans1[i][j]=max(ans1[i][j-1],sd[j][n-(j-i)]);
			}
			ans1[i][1]=max(ans1[i][n],sd[1][i-1]);
			for(int j=2;j<i;j++){
				ans1[i][j]=max(ans1[i][j-1],sd[j][n-(n+j-i)]);
			}
		}
//		for(int i=1;i<=n;cout<<'\n',i++)
//			for(int j=1;j<=n;j++)cout<<ans1[i][j]<<' ';
		int aans=ans1[1][3]+ans1[3][1];
		for(int i=1;i<n;i++)
			for(int j=i+2;j<=n-(i==1);j++)
				aans=min(aans,ans1[i][j]+ans1[j][i]);
		cout<<aans<<'\n';
	}
	return 0;
}