#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<typename T>
ostream& operator << (ostream &out,const vector<T>&x){
	if(x.empty())return out<<"[]";
	out<<'['<<x[0];
	for(int len=x.size(),i=1;i<len;i++)out<<','<<x[i];
	return out<<']';
}
template<typename T>
vector<T> ary(const T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
template<typename T>
void debug(T x){
	cerr<<x<<'\n';
}
template<typename T,typename ...S>
void debug(T x,S ...y){
	cerr<<x<<' ',debug(y...);
}
struct vec{
	int x,y;
};
vec operator - (const vec &a,const vec &b){
	return {a.x-b.x,a.y-b.y};
}
ll dot(const vec &a,const vec &b){
	return 1ll*a.x*b.x+1ll*a.y*b.y;
}
ll dis2(const vec &a){
	return dot(a,a);
}
const int N=1e4+10;
int T,n;
vec a[N];
ll f[N][N];
void get(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&a[i].x,&a[i].y);
	}
	for(int i=1;i<=n+n;i++){
		for(int j=1;j<=n+n;j++){
			f[i][j]=0;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			ll d=dis2(a[i]-a[j]);
			f[i][j]=f[j][i+n]=f[i+n][j+n]=d;
		}
	}
	for(int i=n+n-1;i>=1;i--){
		for(int j=i+1;j<=n+n;j++){
			f[i][j]=max({f[i+1][j],f[i][j-1],f[i][j]});
		}
	}
	ll ans=LONG_LONG_MAX;
	for(int i=1;i<=n;i++){
		for(int j=i+2;j+(i==1)<=n;j++){
			ans=min(ans,f[i][j]+f[j][i+n]);
		}
	}
	printf("%lld\n",ans);
}
int main(){
	for(scanf("%d",&T);T--;)get();
	return 0;
}