#include<iostream>
#include<cstdio>
using namespace std;
const int N=5005;
struct Point
{
  int x,y;
  Point(){x=0,y=0;}
  Point(const int &_x,const int &_y):x(_x),y(_y) {}
  friend Point operator - (const Point &a,const Point &b)
  {
    return Point(a.x-b.x,a.y-b.y);
  }
  friend long long cross(const Point &a,const Point &b)
  {
    return (long long)a.x*b.y-(long long)a.y*b.x;
  }
  friend long long dot(const Point &a,const Point &b)
  {
    return (long long)a.x*b.x+(long long)a.y*b.y;
  }
};
long long distance2(const Point &a,const Point &b)
{
  return (long long)(a.x-b.x)*(a.x-b.x)+(long long)(a.y-b.y)*(a.y-b.y);
}
int n;
Point p[N*2];
long long f[N*2][N*2];
long long dfs(int l,int r)
{
  if(l==r) return f[l][r]=0;
  if(f[l][r]!=-1) return f[l][r];
  return f[l][r]=max(max(dfs(l+1,r),dfs(l,r-1)),distance2(p[l],p[r]));
}
void solve()
{
  cin>>n;
  for(int i=1;i<=n;i++)
    cin>>p[i].x>>p[i].y;
  for(int i=n+1;i<=n*2;i++)
    p[i]=p[i-n];
  for(int i=1;i<=n*2;i++) 
    for(int j=1;j<=n*2;j++)
      f[i][j]=-1;
  long long ans=4e18;
  for(int i=1;i<=n;i++)
    for(int j=i+1;j<=n;j++)
      if(cross(p[j]-p[i],p[i+1]-p[i])!=0&&cross(p[i]-p[j],p[j+1]-p[j])!=0) ans=min(ans,dfs(i,j)+dfs(j,i+n));
  cout<<ans<<"\n";
  return;
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr),cout.tie(nullptr);
  int T;
  cin>>T;
  while(T--)
    solve();
  return 0;
}