#include<bits/stdc++.h>
#define lowbit(x) (x&(-x))
#define ll long long
#define int long long
#define rep(x,a,b) for(int x=a;x<=b;x++)
#define pre(x,a,b) for(int x=a;x>=b;x--)
#define endl "\n"
#define pb push
#define pii pair<ll,ll>
#define psi pair<string, ll>
#define de cout<<1;
#define mem(a,x) memset(a,x,sizeof a)
#define ls u << 1
#define rs u << 1 | 1
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
const int mod1 = 998244353;
const int mod2 = 1e9 + 7;
const int N = 1e6 + 60;
int n, m, k;
int number;
int x[N], y[N], nx[N], la[N];
int dp[5050][5050];
int c(int a, int b, int c, int d)
{
	return (a - c) * (a - c) + (b - d) * (b - d);
}
int ma(int x, int y, int z)
{
	return max(max(x, y), z);
}
bool check(int a, int b, int c)
{
	int w = (x[a] - x[b]) * (y[a] - y[c]) - (y[a] - y[b]) * (x[a] - x[c]);
	return w != 0;
}
void solve()
{
	cin >> n;
	rep(i, 1, n)
	rep(j, 1, n)
	dp[i][j] = 0;
	rep(i, 1, n) cin >> x[i] >> y[i];
	rep(i, 1, n) nx[i] = (i % n) + 1, la[i] = (i - 1) > 0 ? (i - 1) : n;
	rep(len, 2, n)
	{
		rep(l, 1, n)
		{
			int r = (l + len - 1) % n;
			if(r == 0) r = n;
			dp[l][r] = ma(dp[nx[l]][r], dp[l][la[r]], c(x[l], y[l], x[r], y[r]));
		}
	}//cout<<dp[2][6];
	int ans = 9e18;
	rep(i, 1, n)
	{
		for(int j = nx[i]; j != i; j = nx[j])
		{
			if(j == nx[i] || j == la[i]) continue;
			if(check(i, j, nx[i])) 
			{
				ans = min(ans, dp[i][j] + dp[j][i]);
				//if(ans==16) cout<<i<<" "<<j<<" "<<nx[i]<<endl;
			}
		}
	}
	cout << ans << endl;
}
signed main()
{
	IOS;
	int _;
	cin >> _;
	// _ = 1;
	while(_ -- )
	{
		number++;
		solve();
	}
	return 0;
}