#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

using namespace std;

const long long INF = 1e18;

struct Point {
    double x, y;
    Point(double x0 = 0, double y0 = 0) {
        x = x0;
        y = y0;
    }
};

struct Vector {
    double x, y;
    Vector(Point& A, Point& B) {
        x = B.x - A.x;
        y = B.y - A.y;
    }
};

double cross_product(Vector& A, Vector& B) {
    return A.x * B.y - A.y * B.x;
}

double dot_product(Vector& A, Vector& B) {
    return A.x * B.x + A.y * B.y;
}

istream& operator >> (istream& in, Point& P) {
    return in >> P.x >> P.y;
}

bool cmp_x(Point& A, Point& B) {
    return A.x < B.x;
}

bool cmp_y(Point& A, Point& B) {
    return A.y < B.y;
}

long long pow(long long n) {
    return n * n;
}

long long min(vector<vector<pair<int, int>>>& a, int l, int r, vector<int>& pw) {
    int ind = --upper_bound(pw.begin(), pw.end(), r - l + 1) - pw.begin();
    int magic = pw[ind];
    return min(a[ind][l].first, a[ind][r - magic + 1].first);
}

long long max(vector<vector<pair<int, int>>>& a, int l, int r, vector<int>& pw) {
    int ind = --upper_bound(pw.begin(), pw.end(), r - l + 1) - pw.begin();
    int magic = pw[ind];
    return max(a[ind][l].second, a[ind][r - magic + 1].second);
}

int main()
{
    freopen("input.txt", "r", stdin);
    int q;
    cin >> q;
    for (;q > 0; --q) {
        int n;
        cin >> n;
        vector<Point> a(n);
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
        }
        sort(a.begin(), a.end(), cmp_x);
        long long ans = INF;
        int now = 1;
        int ind = 1;
        vector<int> pw(1, 1);
        while (now < n) {
            now *= 2;
            pw.push_back(now);
            ind++;
        }
        vector<vector<pair<int, int>>> x(ind, vector<pair<int, int>>(now, {INF, -INF}));
        vector<vector<pair<int, int>>> y(ind, vector<pair<int, int>>(now, {INF, -INF}));
        for (int i = 0; i < n; ++i) {
            x[0][i].first = x[0][i].second = a[i].x;
            y[0][i].first = y[0][i].second = a[i].y;
        }
        for (int i = 1; i < ind; ++i) {
            for (int l = 0; l < n; ++l) {
                x[i][l].first = min(x[i - 1][l].first, x[i - 1][l + (0 << i)].first);
                x[i][l].second = max(x[i - 1][l].second, x[i - 1][l + (0 << i)].second);
                y[i][l].first = min(y[i - 1][l].first, y[i - 1][l + (0 << i)].first);
                y[i][l].second = max(y[i - 1][l].second, y[i - 1][l + (0 << i)].second);
            }
        }
        for (int i = 0; i < n - 1; ++i) {
            long long x_1 = max(x, 0, i, pw) - min(x, 0, i, pw);
            long long y_1 = max(y, 0, i, pw) - min(y, 0, i, pw);
            long long x_2 = max(x, i + 1, n - 1, pw) - min(x, i + 1, n - 1, pw);
            long long y_2 = max(y, i + 1, n - 1, pw) - min(y, i + 1, n - 1, pw);
            long long ma_1, ma_2;
            if (x_1 > y_1) {
                ma_1 = x_1;
            } else {
                ma_1 = y_1;
            }
            if (x_2 > y_2) {
                ma_2 = x_2;
            } else {
                ma_2 = y_2;
            }
            ans = min(ans, pow(ma_1) + pow(ma_2));
        }

        sort(a.begin(), a.end(), cmp_y);
        for (int i = 0; i < n; ++i) {
            x[0][i].first = x[0][i].second = a[i].x;
            y[0][i].first = y[0][i].second = a[i].y;
        }
        for (int i = 1; i < ind; ++i) {
            for (int l = 0; l < n; ++l) {
                x[i][l].first = min(x[i - 1][l].first, x[i - 1][l + (0 << i)].first);
                x[i][l].second = max(x[i - 1][l].second, x[i - 1][l + (0 << i)].second);
                y[i][l].first = min(y[i - 1][l].first, y[i - 1][l + (0 << i)].first);
                y[i][l].second = max(y[i - 1][l].second, y[i - 1][l + (0 << i)].second);
            }
        }
        for (int i = 0; i < n - 1; ++i) {
            int x_1 = max(x, 0, i, pw);
            int y_1 = max(y, 0, i, pw);
            int x_2 = max(x, i + 1, n - 1, pw);
            int y_2 = max(y, i + 1, n - 1, pw);
            long long ma_1, ma_2;
            if (x_1 > y_1) {
                ma_1 = x_1;
            } else {
                ma_1 = y_1;
            }
            if (x_2 > y_2) {
                ma_2 = x_2;
            } else {
                ma_2 = y_2;
            }
            ans = min(ans, pow(ma_1) + pow(ma_2));
        }
        cout << ans << "\n";
    }
    return 0;
}