#include <bits/stdc++.h>

#define N 5005
#define inf 5000000000000000000ll

typedef long long ll;

using namespace std;

int n;
ll f[N][N];
struct vec
{
	int x,y;
	inline vec operator-(const vec& b)const{return {x-b.x,y-b.y};}
}p[N];

ll calc(int,int);
ll dis2(vec a,vec b){return 1ll*(a.x-b.x)*(a.x-b.x)+1ll*(a.y-b.y)*(a.y-b.y);}
ll cro(vec a,vec b){return 1ll*a.x*b.y-1ll*a.y*b.x;}

int main()
{
	ll ans;
	int i,j,T;
	scanf("%d",&T);
	while(T--)
	{
		ans=inf;
		scanf("%d",&n);
		for(i=1;i<=n;++i)
			scanf("%d %d",&p[i].x,&p[i].y);
		for(i=0;i<=n;++i)
			for(j=0;j<=n;++j)
				f[i][j]=-1;
		for(i=1;i<=n;++i)
			for(j=i+2;j<=n;++j)
				if(j%n+1!=i&&cro(p[i+1]-p[i],p[j]-p[i])!=0)
					ans=min(ans,calc(i,j)+calc(j,i));
		printf("%lld\n",ans);
	}
	return 0;
}
ll calc(int l,int r)
{
	if(l==r)return 0;
	if(f[l][r]!=-1)return f[l][r];
	return f[l][r]=max(dis2(p[l],p[r]),max(calc(l%n+1,r),calc(l,(r+n-2)%n+1)));
}