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

typedef long long ll;

const int N = 5010;

ll dp[N][N], f[N][N];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int T;
	cin >> T;
	while(T -- ) {
		int n;
		cin >> n;
		vector<pair<int, int>> arr(n);
		for(int i = 0; i < n; i ++ ) cin >> arr[i].first >> arr[i].second;
		reverse(arr.begin(), arr.end());

		auto getdis = [&](int u, int v) -> ll {
			ll dx = arr[u].first - arr[v].first;
			ll dy = arr[u].second - arr[v].second;
			return dx * dx + dy * dy;
		};

		for(int i = 0; i < n; i ++ ) {
			for(int j = 0; j < n; j ++ ) {
				dp[i][j] = f[i][j] = 0;
			}
		}
		for(int i = 0; i < n; i ++ ) {
			for(int j = 1; j < n; j ++ ) {
				f[i][j] = getdis(i, (i - j + n) % n);
			}
			for(int j = 1; j < n; j ++ ) {
				f[i][j] = max(f[i][j], f[i][j - 1]);
			}
		}
		
		for(int j = 1; j < n; j ++ ) {
			for(int k = j, t = 0; k >= 1; k -- , t ++ ) {
				dp[0][j] = max(dp[0][j], f[(0 - t + n) % n][k]);
			}
		}
		for(int i = 1; i < n; i ++ ) {
			for(int j = 1; j < n; j ++ ) {
				dp[i][j] = max(dp[i - 1][j - 1], f[i][j]);
			}
		}

		ll ans = 4e18;
		for(int i = 0; i < n; i ++ ) {
			for(int j = i + 1; j < n; j ++ ) {
				if(j - i >= 2 && n - j + i >= 2) {
					ll res = dp[j][j - i] + dp[i][n + i - j];
					ans = min(ans, res);
				}
			}
		}
		cout << ans << '\n';
	}
	return 0;
}