#include<bits/stdc++.h>
#define int long long

using namespace std;

int dist(pair<int, int> &A, pair<int, int> &B) {
    return (A.first - B.first) * (A.first - B.first) + (A.second - B.second) * (A.second - B.second);
}

int solve(vector<pair<int, int>> &p, int x, int dir) {
    int n = p.size();
    int l = 0, r = n - 2, res = 0;

    while (l <= r) {
        int mid = l + r >> 1;
        int pos = (x + mid * dir) % n;
        if (pos < 0) pos += n;
        res = max(res, dist(p[pos], p[x]));
        if (dist(p[(pos + dir + n) % n], p[x]) - dist(p[pos], p[x]) >= 0) {
            l = mid + 1;
        }
        else {
            r = mid - 1;
        }
    }

    return res;;
}

signed main(){
    ios::sync_with_stdio(0); cin.tie(0);
//    freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);

    int t;

    cin >> t;

    while (t--) {
        int n;

        cin >> n;

        vector<pair<int, int>> p(n);

        for (auto &[u, v]: p) {
            cin >> u >> v;
        }

        int res = 4E18;

        for (int i = 0 ; i < n ; i++) {
            if (sqrtl(dist(p[i], p[(i + 1) % n])) + sqrtl(dist(p[(i + 1) % n], p[(i + 2) % n])) == sqrtl(dist(p[i], p[(i+2)%n]))) {
                continue;
            }
            if (sqrtl(dist(p[i], p[(i + 3) % n])) + sqrtl(dist(p[(i + 3) % n], p[(i + 2) % n])) == sqrtl(dist(p[i], p[(i+2)%n]))) {
                continue;
            }
            int d1 = solve(p, i, -1);
            int d2 = solve(p, (i+2) % n, 1);
            int d = max({
                dist(p[i], p[(i+1)%n]),
                dist(p[i], p[(i+2)%n]),
                dist(p[(i+1)%n], p[(i+2)%n])
            });

            // cout << i << " " << d1 << " " << d2 << " " << d << " DEBUG\n";

            res = min(res, max(d1, d2) + d);
        }

        cout << res << "\n";
    }
    return 0;
}