#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <utility>
#include <array>

using namespace std;

typedef long long ll;

template<class T> int sgn(T x) { return (x > 0) - (x < 0);}
template <class T>
struct Point{
    typedef Point P;
    T x, y;
    explicit Point(T x=0, T y=0): x(x), y(y){}
    bool operator<(P p) const {return tie(x, y) < tie(p.x, p.y);}
    P operator+(P p)const {return P(x+p.x, y+p.y);}
    P operator-(P p)const {return P(x-p.x, y-p.y);}
    T dot(P p)const{return x * p.x + y * p.y;}
    T cross(P p) const { return x * p.y - y * p.x;}
    T cross(P a, P b) const {return (a-*this).cross(b-*this);}
    T dist2() const {return x * x + y * y;}
};

template<class P> bool onSegment(P s, P e, P p){
    return p.cross(s, e) == 0 && (s - p).dot(e - p) <= 0;
}

typedef Point<ll> P;
array<P, 2> hullDiameter(vector<P> S){
    int n = S.size(), j = n < 2 ? 0 : 1;
    pair<ll, array<P, 2>> res({0, {S[0], S[0]}});
    for(int i = 0; i < j; ++i){
        for(;;j = (j + 1) % n){
            res = max(res, {(S[i] - S[j]).dist2(), {S[i], S[j]}});
            if((S[(j + 1) % n] - S[j]).cross(S[i + 1] - S[i]) >=  0)
                break;
        }   
    }
    return res.second;
}

const int N = 5e3 + 3;
int n;
P p[N];

int nxt(int x){
    return (x + 1) % n;
}
int prv(int x){
    return (x + n - 1) % n;
}

ll diam(int l, int r){
    vector<P> v;
    for(int x = l; x != r; x = nxt(x)){
        while(v.size() >= 2 && onSegment(p[x], v.back(), v[(int)v.size() - 2]))
            v.pop_back();
        v.push_back(p[x]);
    }
    for(int x: vector<int>{r, l}){
        while(v.size() >= 2 && onSegment(p[x], v.back(), v[(int)v.size() - 2]))
            v.pop_back();
        v.push_back(p[x]);
    }
    v.pop_back();
    auto [p1, p2] = hullDiameter(v);
    return (p1 - p2).dist2();
}

void solve(){
    cin >> n;
    for(int i = 0; i < n; ++i){
        cin >> p[i].x >> p[i].y;
    }

    int j = 0;
    ll ans = LLONG_MAX;
    for(int i = 0; i < n; ++i){
        // cout << i << " " << j << " i j" << endl;
        while(i == j || nxt(i) == j)
            j = nxt(j);

        while(onSegment(p[i], p[nxt(i)], p[j]))
            j = nxt(j);

        if(nxt(j) == i)
            continue;

        if(onSegment(p[j], p[nxt(j)], p[i]))
            continue;

        ll d1 = diam(i, j);
        ll d2 = diam(j, i);
        ans = min(ans, d1 + d2);
        // cout << i << " " << j << " - " << d1 << " " << d2 << "\n";

        if(d1 < d2){
            j = nxt(j);
            i = i - 1;
            continue;
        }
        else{
            continue;
        }
    }

    cout << ans << "\n";
}

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

    int t;
    cin >> t;
    while(t--)
        solve();
}

answer.code: In function ‘void solve()’:
answer.code:84:14: error: ‘LLONG_MAX’ was not declared in this scope
   84 |     ll ans = LLONG_MAX;
      |              ^~~~~~~~~
answer.code:9:1: note: ‘LLONG_MAX’ is defined in header ‘<climits>’; did you forget to ‘#include <climits>’?
    8 | #include <numeric>
  +++ |+#include <climits>
    9 | #include <utility>