#include<bits/stdc++.h>
using namespace std;

#define double long double
#define MAXN 5005
#define eps 1e-6
#define INF 3e18

struct vec2{
	double x,y;
	vec2(){}
	vec2( double a , double b ): x(a),y(b){}
	inline vec2 operator +( vec2 B ){ return vec2( x + B.x , y + B.y ); }
	inline vec2 operator -( vec2 B ){ return vec2( x - B.x , y - B.y ); }
}p[MAXN];

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

inline double dist( vec2 A , vec2 B ){ return ( A.x - B.x ) * ( A.x - B.x ) + ( A.y - B.y ) * ( A.y - B.y ); }

inline bool online( vec2 A , vec2 B , vec2 C ){ return fabs( Cross( A - C , B - C ) ) < eps; }

int n;
double f[MAXN][MAXN],g[MAXN][MAXN];

inline void solve(){
	scanf("%d",&n);
	for( int i = 1 ; i <= n ; i ++ ) scanf("%Lf%Lf",&p[i].x,&p[i].y);
	for( int i = 1 ; i < n ; i ++ ) f[i][i + 1] = dist( p[i] , p[i + 1] );
	for( int len = 3 ; len <= n ; len ++ ){
		for( int l = 1 ; l + len - 1 <= n ; l ++ ){
			int r = l + len - 1;
			if( online( p[l] , p[l + 1] , p[r] ) || ( ( l > 1 ) && online( p[l] , p[l - 1] , p[r] ) ) ) f[l][r] = INF;
			else f[l][r] = max( max( f[l + 1][r] , f[l][r - 1] ) , dist( p[l] , p[r] ) );
		}
	}
	// for( int l = 1 ; l < n ; l ++ ){
		// for( int r = l + 1 ; r <= n ; r ++ ){
			// cerr << l << " " << r << " " << f[l][r] << "\n";
		// }
	// }
	// cerr << "\n";
	g[1][n] = dist( p[1] , p[n] );
	for( int len = 3 ; len <= n ; len ++ ){
		for( int l = 1 ; l < len ; l ++ ){
			int r = n - ( len - l ) + 1;
			if( ( l == 1 ) && online( p[1] , p[n] , p[r] ) ) g[l][r] = INF;
			else if( ( r == n ) && online( p[1] , p[n] , p[l] ) ) g[l][r] = INF;
			else if( l == 1 ) g[l][r] = max( max( g[l][r + 1] , f[r][n] ) , dist( p[l] , p[r] ) );
			else if( r == n ) g[l][r] = max( max( g[l - 1][r] , f[1][l] ) , dist( p[l] , p[r] ) );
			else g[l][r] = max( max( g[l - 1][r] , g[l][r + 1] ) , dist( p[l] , p[r] ) );
			
		}
	}
	// for( int l = 1 ; l < n ; l ++ ){
		// for( int r = l + 1 ; r <= n ; r ++ ){
			// cerr << l << " " << r << " " << g[l][r] << "\n";
		// }
	// }
	// cerr << "\n";
	double Ans = INF;
	for( int l = 1 ; l <= n - 2 ; l ++ )
		for( int r = l + 2 ; r <= ( ( l == 1 ) ? n - 1 : n ) ; r ++ )
			Ans = min( Ans , f[l][r] + g[l][r] );
	printf("%lld\n",(long long)Ans);
	cerr << "\n";
}

signed main(){
	int testcase; scanf("%d",&testcase);
	while( testcase -- ) solve();
	return 0;
}