#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#define pb push_back
#define mp make_pair
#define x first
#define y second

using namespace std;

typedef long double ld;
typedef long long ll;
using pii = pair<int, int>;
using vpii = vector<pii>;
using vi = vector<int>;
using vl = vector<ll>;
using vvl = vector<vl>;

ll sqd(pii p) {
	return ll(p.x) * p.x + ll(p.y) * p.y;
}
ll sqd(pii p, pii q) {
	return sqd({ p.x - q.x, p.y - q.y });
}
int sum(int a, int b, int n) {
	if ((a += b) >= n) a -= n;
	return a;
}
int dif(int a, int b, int n) {
	if ((a -= b) < 0) a += n;
	return a;
}
ll find_ans(const vpii& v) {
	const int n = v.size();
	vvl diag(n, vl(n));
	for (int j = 0; j < n; ++j)
		for (int i = j, z = 0; z < n - 1; ++z) {
			i = dif(i, 1, n);
			diag[i][j] = max(diag[sum(i, 1, n)][j], sqd(v[i], v[j]));
		}

	vvl seg(n, vl(n));
	for (int i = 0; i < n; ++i)
		for (int j = i, z = 0; z < n - 1; ++z) {
			j = sum(j, 1, n);
			seg[i][j] = max(seg[i][dif(j, 1, n)], diag[i][j]);
		}

	ll ans = 1e18;
	for (int i = 0; i < n; ++i)
		for (int j = i + 1; j < n; ++j) {
			ll q = seg[i][j] + seg[j][i];
			if (q < ans)
				ans = q;
		}
	cerr << "DIAG:\n";
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			cerr << diag[i][j] << " \n"[j == n - 1];
	cerr << "SEG:\n";
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			cerr << seg[i][j] << " \n"[j == n - 1];
	return ans;
}

void solve_test() {
	int n;
	cin >> n;
	vpii v(n);
	for (int i = 0; i < n; ++i)
		cin >> v[i].x >> v[i].y;
	cout << find_ans(v) << '\n';
}

void solve_tests() {
	int t = 1;
	cin >> t;
	for (int i = 0; i < t; ++i)
		solve_test();
}

int main() {
#ifdef HOME
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(0); cin.tie(0);
	solve_tests();
	return 0;
}

/*
* TEST:
6
10 4
9 7
5 7
4 5
6 4
9 3
* DIAG:
0 10 34 37 18 32
37 0 16 29 18 32
37 29 0 5 10 32
37 29 34 0 5 29
16 18 34 37 0 10
2 16 34 37 18 0
* SEG:
0 10 34 37 37 37
37 0 16 29 29 32
37 37 0 5 10 32
37 37 37 0 5 29
16 18 34 37 0 10
2 16 34 37 37 0*/