// Super Idol的笑容
//    都没你的甜
//  八月正午的阳光
//    都没你耀眼
//  热爱105°C的你
// 滴滴清纯的蒸馏水

#include <bits/stdc++.h>

#define double long double
#define int long long
using namespace std;
using PII = pair<int,int>;
using ll = long long;

int n;

struct point{long long x,y;}pk[5010 * 2], s[5010 * 2],tmp;
int inf = 1ll << 62;
int tot;

long long f(point c1,point a,point c2,point b){//叉积
	return (a.x-c1.x)*(b.y-c2.y)-(b.x-c2.x)*(a.y-c1.y);
}

long long sqr(long long x){  return x*x;}

long long dis(point m,point n){
	return sqr(abs(m.x-n.x))+sqr(abs(m.y-n.y));
}

bool cmp(point p,point q){//其他大佬好像都是用atan2直接求的极角大小，我用的叉积。
	long long t=f(pk[0],p,pk[0],q);
	if(t>0)//如果叉积为正，则说明转的方向是对的
		return 1;
	if(!t)//如果出现三点共线的情况就比较距离
		return dis(pk[0],p)<dis(pk[0],q);
	return 0;
}


double mianji(point a,point b,point c){//求三点组成的三角形的面积 蒟蒻只会用割补法
	double xi=min(a.x,min(b.x,c.x));
	double yi=min(a.y,min(b.y,c.y));
	double xa=max(a.x,max(b.x,c.x));
	double ya=max(a.y,max(b.y,c.y));
	double ansi=(xa-xi)*(ya-yi);
	ansi-=(max(a.x,b.x)-min(a.x,b.x))*(max(a.y,b.y)-min(a.y,b.y))/2;
	ansi-=(max(a.x,c.x)-min(a.x,c.x))*(max(a.y,c.y)-min(a.y,c.y))/2;
	ansi-=(max(c.x,b.x)-min(c.x,b.x))*(max(c.y,b.y)-min(c.y,b.y))/2;
	return ansi;
}

ll dp[5010 * 2][5010 * 2];
ll dist[5010 * 2][5010 * 2];

void solve() {
	tot = 0;
	cin >> n;
	for(int i = 0; i < n; i ++) cin >> s[i].x >> s[i].y;
	for(int i = n; i < 2 * n; i ++) s[i] = s[i - n];
	for(int i = 0; i < 2 * n; i ++) {
		for(int j = i + 1; j < 2 * n; j ++) {
			dist[i][j] = max(dist[i][j - 1], dis(s[i], s[j]));
		}
	}
	for(int len = 2; len <= n; len ++) {
		for(int l = 0; l + len - 1 < 2 * n; l ++) {
			int r = l + len - 1;
			dp[l][r] = max(dp[l + 1][r], dist[l][r]);
		}
	}
	double ans = 0;
	for(int i = 2; i < n; i ++) {
		ans += mianji(s[0], s[i - 1], s[i]);
	}
	ll maxs = 1ll << 62;
	for(int i = 0; i < n; i ++) {
		double sum = 0;
		for(int j = i + 2; j <= i + n - 2; j ++) {
			sum += mianji(s[i], s[j - 1], s[j]);
			double g1 = sum;
			double g2 = ans - sum;
			if(g1 && g2) {
				maxs = min({dp[i][j] + dp[j][i + n], maxs});
			}
		}
	}
	cout << maxs << "\n";
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
	cin >> t;
	while(t--) {
		solve();
	}
}