#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=5e3+10;
int Dp[2*maxn][maxn],T,n,lp[2*maxn][maxn];
bool comlin[2*maxn][maxn];
struct node{
	int x,y;
}p[maxn];
int Dis(int i,int j){
	return (p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y);
}
signed main(){
	scanf("%lld",&T);
	while(T--){
		scanf("%lld",&n);
		for(int i=1;i<=n;i++) scanf("%lld%lld",&p[i].x,&p[i].y),p[i+n]=p[i];
		for(int j=0;j<n;j++)
			for(int i=1;i+j<=2*n;i++)
				if(j==0) Dp[i][j]=0;
				else Dp[i][j]=max(Dp[i][j-1],Dis(i,i+j));
		for(int i=2*n;i>=1;i--)
			for(int j=0;j<n&&i+j<=2*n;j++){
				if(j==0) lp[i][j]=0;
				else lp[i][j]=max(lp[i+1][j-1],Dp[i][j]);
				if(j<=1) comlin[i][j]=1;
				else comlin[i][j]=(comlin[i+1][j-1]&((p[i].x-p[i+1].x)*(p[i+1].y-p[i+2].y)==(p[i].y-p[i+1].y)*(p[i+1].x-p[i+2].x)));
			}
		int ans=1e18;
		for(int i=1;i<=n;i++)
			for(int j=i+2;j<=n;j++){
				if(comlin[i][j-i]||comlin[j][n+i-j]) continue;
				ans=min(ans,lp[i][j-i]+lp[j][n+i-j]);
			}
		printf("%lld\n",ans);
	}
	return 0;
}