#include <bits/stdc++.h>
#define fr first
#define sc second
#define all(a) (a).begin(), (a).end()
#define unique(a) a.resize(unique(a.begin(), a.end()) - a.begin())

using namespace std;

#ifdef ONPC
mt19937 rnd(223);
#else
mt19937 rnd(chrono::high_resolution_clock::now()
			.time_since_epoch().count());
#endif

#define TIME (clock() * 1.0 / CLOCKS_PER_SEC)

using ll = long long;
using ld = double;

const int maxn = 1e4 + 100, inf = 1e9 + 100;

ll dp[maxn][maxn];

#define cin if(1)cin

void solve() {
    int n;
    n = 5e3;
    cin >> n;
    vector<pair<int, int>> a(2 * n);
    auto cross = [&](pair<int, int> x, pair<int, int> y) -> ll {
        return x.fr * (ll)y.sc - x.sc * (ll)y.fr;
    };
    for (int i = 0; i < n; i++) {
        a[i].fr = rnd() % 100000 + 1;
        a[i].sc = rnd() % 100000 + 1;
        cin >> a[i].fr >> a[i].sc;
    }
    for (int i = n; i < 2 * n; i++)
        a[i] = a[i - n];
    for (int i = 0; i < 2 * n; i++)
        fill(dp[i], dp[i] + 2 * n, 0);
    for (int i = 0; i < 2 * n; i++)
        for (int j = i + 1; j < 2 * n; j++)
            dp[i][j] = (a[i].fr - a[j].fr) * (a[i].fr - a[j].fr) + (a[i].sc - a[j].sc) * (a[i].sc - a[j].sc);
    for (int len = 1; len < 2 * n; len++)
        for (int l = 0; l + len < 2 * n; l++) {
            int r = l + len;
            dp[l][r] = max({dp[l][r], dp[l + 1][r], dp[l][r - 1]});
        }
    vector<int> last(2 * n);
    for (int i = 0; i < 2 * n; i++) {
        ll s = 0;
        last[i] = i;
        for (int j = i + 1; j < 2 * n; j++) {
            s += cross(a[j - 1], a[j]);
            if (s + cross(a[j], a[i]) == 0)
                last[i]++;
            else
                break;
        }
    }
    ll ans = numeric_limits<ll>::max();
    for (int l = 0; l < n; l++)
        for (int r = l + 1; r < n; r++) {
            ll x = dp[l][r], y = dp[r][l + n];
            if (last[l] < r && last[r] < l + n)
                ans = min(ans, x + y);
        }
    cout << ans << '\n';
}

int main() {
#ifdef ONPC
    freopen("../a.in", "r", stdin);
//    freopen("../a.out", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout << fixed;
    cout.precision(20);
    int ts;
    ts = 1;
    cin >> ts;
    while (ts--)
        solve();
    cerr << "\n\nConsumed " << TIME << endl;
}