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

#define int __int128
#define MAXN 5005
#define INF 8e18

inline int read(){
	int x = 0; char ch = getchar();
	while( ch < '0' || ch > '9' ) ch = getchar();
	while( ch >= '0' && ch <= '9' ) x = ( x << 3 ) + ( x << 1 ) + ch - 48,ch = getchar();
	return x;
}

void write( int x ){
	if( x >= 10 ) write( x / 10 );
	putchar( x % 10 + 48 );
}

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(){
	n = read();
	for( int i = 1 ; i <= n ; i ++ ) p[i].x = read(),p[i].y = read();
	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] ) );
			//cerr << l << " " << r << " " << l << " " << r + 1 << " " << r << " " << n << " " << g[l][r] << "\n";
		}
	}
	// for( int l = 1 ; l <= n - 1 ; l ++ ){
		// for( int r = l + 1 ; r <= n ; r ++ ){
			// cerr << l << " " << r << " " << f[l][r] << " " << g[l][r] << "\n";
		// }
	// }
	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;
			if( f[l][r] && g[l][r] ) 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();
	write( Ans ); puts("");
}

signed main(){
	int testcase = read();
	while( testcase -- ) solve();
	return 0;
}