#include<bits/stdc++.h>
using namespace std;
#define int long long
#define Double long double
const int MAXN = 1e6 + 10;
const Double eps = 1e-10;
const Double PI = acosl(-1.0);
int N,M,K,Q;
int a[MAXN];

Double torad(Double deg){
    return deg / 180 * PI;
}

int dcmp(Double x){
    if(fabs(x) < eps) return 0;
    else return x < 0 ? -1 : 1;
}

struct Point{
    int x,y;
    Point(int x=0,int y=0):x(x),y(y){}
    void read(){
        scanf("%lld %lld",&x,&y);
    }
};

typedef vector<Point> Polygon;
typedef Point Vector;

inline Vector operator + (Vector A,Vector B){
    return Vector(A.x+B.x,A.y+B.y);
}

inline Vector operator - (Vector A,Vector B){
    return Vector(A.x - B.x , A.y - B.y);
}

inline Vector operator * (Vector A,Double p){
    return Vector(A.x * p,A.y * p);
}

inline Vector operator / (Vector A,Double p){
    return Vector(A.x / p,A.y / p);
}

inline bool operator < (Point A,Point B){
    return A.x < B.x || (A.x == B.x && A.y < B.y);
}

inline bool operator == (Point A,Point B){
    return dcmp(A.x - B.x) == 0 && dcmp(A.y - B.y) == 0;
}

inline int Dot(Vector A,Vector B){
    return A.x * B.x + A.y * B.y;
}

inline int Length(Vector A){
    return Dot(A , A);
}

inline Double Angle(Vector A,Vector B){
    return acos(Dot(A,B) / Length(A) / Length(B));
}

inline Double angle(Vector v){
    return atan2(v.y,v.x);
}

inline int Cross(Vector A,Vector B){
    return A.x * B.y - A.y * B.x;
}

inline Vector Unit(Vector v){
    return v / Length(v);
}

inline Vector Normal(Vector v){
    return Point(-v.y,v.x) / Length(v);
}

inline Vector Rotate(Vector A, Double rad){
    return Vector(A.x * cos(rad) - A.y * sin(rad),A.x * sin(rad) + A.y * cos(rad));
}

inline Double Area2(Point A,Point B,Point C){
    return Cross(B - A,C - A);
}

inline Point GetLineIntersection(Point p,Vector v,Point q,Vector w){
    Vector u = p - q;
    Double t = Cross(v,p-q) / Cross(v,w);
    return p + v*t;
}

inline Point GetLineProjection(Point P,Point A,Point B){
    Vector v = B - A;
    return A + v * (Dot(v,P-A)) / Dot(v,v);
}

inline Double DistanceToLine(Point P,Point A,Point B){
    Vector v1 = B - A, v2 = P - A;
    return fabs(Cross(v1,v2)) / Length(v1);
}

inline bool OnSegment(Point P,Point A,Point B){
    return dcmp(Cross(A-P,B-P)) == 0 && dcmp(Dot(A-P,B-P)) <= 0;
}

inline void getLineGeneralEquation(Point A,Point B,Double &a,Double &b,Double &c){
    a = B.y - A.y;
    b = A.x - B.x;
    c = - a * A.x - b * A.y;
}

Double DistanceToSegment(Point P,Point A,Point B){
    if(A == B) return Length(P-A);
    Vector v1 = B - A,v2 = P - A,v3 = P-B;
    if(dcmp(Dot(v1,v2)) < 0) return Length(v2);
    else if(dcmp(Dot(v1,v3)) > 0) return Length(v3);
    else return fabs(Cross(v1,v2)) / Length(v1);
}

Point points[2 * MAXN];
int dp[5010][5010];

int query(int l,int r){
    if(l > r) r += N;
    if(dp[l][r-l]) return dp[l][r-l];
    if(l + 1 == r) return Length(points[l] - points[r]);
    int ret = max(query(l,r-1),query(l+1,r));
    ret = max(ret,Length(points[l]-points[r]));
    return dp[l][r-l] = ret;
}

int calc(int x){
    if(x <= 0) x += N;
    if(x >= N + 1) x -= N;
    return x;
}

void prepare(){
	scanf("%lld",&N);
	for(int i = 1;i <= N; i++) points[i].read();
    for(int i = 1;i <= N; i++){
        points[i + N] = points[i];
    }
    for(int i = 1;i <= N; i++){
        for(int k = 0; k <= N; k++){
            dp[i][k] = 0;
        }
    }
    int ans = 9e18;
    for(int i = 1;i <= N; i++){
        for(int j = 2;j <= N - 2; j++){
            int k = calc(i + j);
            if(Cross(points[calc(i+1)]-points[i],points[k]-points[i]) == 0 || Cross(points[calc(i-1)]-points[i],points[k]-points[i]) == 0) continue;
            ans = min(ans,query(i,k)+query(k,i));
        }
    }
    printf("%lld\n",ans);
}

signed main(){
	int T = 1;
	scanf("%lld",&T);
	while(T--){
		prepare();
	}
}