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

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

struct vec2{
	int x,y;
	vec2(){}
	vec2( int a , int 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 int Cross( vec2 A , vec2 B ){ return A.x * B.y - A.y * B.x; }

inline int 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 Cross( A - C , B - C ) == 0; }

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

inline void solve(){
	scanf("%lld",&n);
	for( int i = 1 ; i <= n ; i ++ ) scanf("%lld%lld",&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 == n ) ? 1 : l + 1] , p[r] ) || online( p[l] , p[( l == 1 ) ? n : l - 1] , p[r] ) ) f[l][r] = 0;
			else f[l][r] = max( max( f[l + 1][r] , f[l][r - 1] ) , dist( p[l] , p[r] ) );
		}
	}
	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( online( p[l] , p[( l == n ) ? 1 : l + 1] , p[r] ) || online( p[l] , p[( l == 1 ) ? n : l - 1] , p[r] ) ) g[l][r] = 0;
			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] ) );
			
		}
	}
	int Ans = INF;
	for( int l = 1 ; l <= n - 1 ; l ++ )
		for( int r = l + 1 ; r <= n ; r ++ ){
			if( ( online( p[l] , p[( l == 1 ) ? n : l - 1] , p[r] ) ) || online( p[l] , p[( l == n ) ? 1 : l + 1] , p[r] ) ) continue;
			Ans = min( Ans , f[l][r] + g[l][r] );
		}
	for( int i = 1 ; i <= n ; i ++ )
		for( int j = 1 ; j <= n ; j ++ ) f[i][j] = g[i][j] = 0;
	for( int i = 1 ; i <= n ; i ++ ) p[i] = vec2();
	printf("%lld\n",Ans);
}

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