#include<bits/stdc++.h>
#define endl '\n'
using namespace std;


#define int long long
using ll = long long;
using pii = pair<int, int>;
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int tt = 1;
	cin >> tt;
	while (tt--) {
		int n;
		cin >> n;
		vector<pii>a(n);
		for (int i = 0; i < n; i++) {
			cin >> a[i].first >> a[i].second;
		}
		vector < vector < ll> >dp(n, vector < ll>(n));
		auto dis = [&](pii a, pii b)->ll {
			return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
		}; ll ma = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				dp[i][j] = dis(a[i], a[j]);
				//cout << dp[i][j] << ' ';
				ma = max(dp[i][j], ma);

			}
			//cout << endl;
		}//cout << endl;

		for (int i = 2; i < n; i++) {
			if (0) {
				for (int j = 0; j < n; j++) {
					dp[j][(j + n - 1) % n] = ma;
				}
				continue;
			}
			for (int j = 0; j < n; j++) {
				dp[j][(j + i) % n] = max({ dp[j][(j + i) % n] ,dp[(j + 1) % n][(j + i) % n],dp[j][(j + i - 1) % n] });
			}
		}

		ll ans = 1e18;
		auto cross = [&](pii a, pii b, pii c) ->bool {
			ll x = (a.first - c.first) * (b.second - c.second) - (a.second - c.second) * (b.first - c.first);
			if (x == 0)return 0;
			else return 1;
		};
		for (int i = 2; i < n-1; i++) {
			for (int j = 0; j < n; j++) {
				
				int x = j, y = (j + i) % n;
				if  (i==2&&cross(a[x],a[(x+1)%n],a[y])==0||i==n-2&& cross(a[x], a[(x - 1+n) % n], a[y])==0)continue;
				ans = min(ans, dp[x][y] + dp[y][x]);
				//cout << x<< ' '<<y  << endl;
			}
			
		}
		cout << ans << endl;
	}
}