#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define max(A,B) (A>B? A:B)
#define min(A,B) (A<B? A:B)
#define yes cout<<"Yes\n"
#define no cout<<"No\n"
#define pir(X) pair<X,X>
#define mpr(A,B) make_pair(A,B)
#define fr first
#define sc second
#define sq(x) ((x)*(x))
using namespace std;

const int N=5e3+10;
const db inf=5e18;
const db eps=1e-7;
class Point{
public:
    db x,y,arctan;
    Point(db _x=0,db _y=0) : x(_x),y(_y) {}
    void read() { cin>>x>>y; }
    void print(string s=""){
        cerr<<" Point ["<<s<<"] : x="<<x<<" y="<<y<<'\n';
    }

    Point turn(const db k) const {
        Point p(x*cos(k)-y*sin(k),x*sin(k)+y*cos(k));
        return p;
    }
    Point operator - (const Point &o) const{
        Point ret(x-o.x,y-o.y);
        return ret;
    }
    Point operator + (const Point &o) const{
        Point ret(x+o.x,y+o.y);
        return ret;
    }
    bool operator == (const Point &o) const{
        return x==o.x&&y==o.y;
    }
}p[N];
class Vector2{
public:
    db x,y;
    Vector2(db _x=0,db _y=0): x(_x),y(_y) {}
    void read() { cin>>x>>y; }
    void print(string s=""){
        cerr<<" Vector2 ["<<s<<"] : x="<<x<<" y="<<y<<'\n';
    }

    void assign(db _x,db _y) { x=_x, y=_y; }
    void assign(const Point &a,const Point &b){ // 向量赋值，注意前后形参的顺序
        x=a.x-b.x;
        y=a.y-b.y;
    }
    Vector2 operator + (const Vector2 &o) const {
        return (Vector2){x+o.x,y+o.y};
    }
    Vector2 operator - (const Vector2 &o) const {
        return (Vector2){x-o.x,y-o.y};
    }
    Vector2 operator * (const db a) const {
        return (Vector2){a*x,a*y};
    }
    db operator * (const Vector2 &o) const {
        return x*o.x+y*o.y;
    }
    db operator ^ (const Vector2 &o) const {
        return x*o.y-y*o.x;
    }
    db len() const{
        return sqrt(x*x+y*y);
    }
    db len2() const{
        return x*x+y*y;
    }
    Vector2 unit() const {
        db len=sqrt(x*x+y*y);
        Vector2 l(x/len,y/len);
        return l;
    }
};
db dis(Point a,Point b){
    return sq(a.x-b.x)+sq(a.y-b.y);
}
bool In_line(const Point &a,const Point &b,const Point &c){  // 判断 b 是否在直线 a-c 上
    // if(!(min(a.x,c.x)<=b.x+eps&&b.x<=max(a.x,c.x)+eps)) return false;
    // if(!(min(a.y,c.y)<=b.y+eps&&b.y<=max(a.y,c.y)+eps)) return false;
    Vector2 l1,l2;
    l1.assign(a,b),l2.assign(c,b);
    return fabs(l1^l2)<=eps;
};
db f[N][N];
int n;

void slv(){
    cin>>n;
    for(int i=0;i<n;i++) p[i].read();
    // for(int i=0;i<n;i++){
    //     for(int j=0;j<n;j++) f[i][j]=inf;
    // }
    for(int i=0;i<n;i++) f[i][(i+1)%n]=dis(p[i],p[(i+1)%n]);
    for(int l=2;l<=n;l++){
        for(int i=0;i<n;i++){
            int j=(i+l)%n;
            f[i][j]=max(dis(p[i],p[j]),max(f[(i+1+n)%n][j],f[i][(j-1+n)%n]));
        }
    }
    db ans=inf;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            // cerr<<" i="<<i<<" j="<<j<<" f="<<f[i][j]<<" dis="<<dis(p[i],p[j])<<'\n';
            if(In_line(p[i],p[j],p[(i+1)%n])) continue;
            if(In_line(p[(i-1+n)%n],p[j],p[i])) continue;
            ans=min(ans,f[i][j]+f[j][i]);
        }
    }
    cout<<(ll)round(ans)<<'\n';
    return;
}

void fst_IO(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}

int main(){
    fst_IO();
    int T;
    cin>>T;
    while(T--){
        slv();
    }
    return 0;
}