//  Nikita Golikov, 2023

#include <bits/stdc++.h>

using namespace std;

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;

#ifdef GOLIKOV
  #include "/Users/golikovnik/contests/debug.h"
#else
  #define debug(...) ;
#endif

template <class A, class B>
bool smin(A& x, B&& y) {
  if (y < x) {
    x = y;
    return true;
  }
  return false;
}

template <class A, class B>
bool smax(A& x, B&& y) {
  if (x < y) {
    x = y;
    return true;
  }
  return false;
}

void solveTest() {
  int n; cin >> n;
  vector<pair<int, int>> a(n);
  for (auto& [x, y] : a) {
    cin >> x >> y;
  }
  auto sqr = [&](ll x) {
    return x * x;
  };
  auto Dist = [&](int i, int j) {
    return sqr(a[i].first - a[j].first) + sqr(a[i].second - a[j].second);
  };
  vector dp(2 * n, vector<ll>(2 * n));
  for (int r = 0; r < 2 * n; ++r) {
    for (int l = r - 1; l >= 0; --l) {
      dp[l][r] = max({dp[l + 1][r], dp[l][r - 1], Dist(l % n, r % n)});
      debug(l, r, dp[l][r]);
    }
  }
  ll ans = LLONG_MAX;
  for (int s = 0; s < n; ++s) {
    for (int cnt = 3; n - cnt + 2 >= 3; ++cnt) {
      smin(ans, dp[s][s + cnt - 1] + dp[s + cnt - 1][s + n]);
    }
  }
  cout << ans << '\n';
}

int main() {
#ifdef GOLIKOV
  assert(freopen("in", "rt", stdin));
  auto _clock_start = chrono::high_resolution_clock::now();
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int tests_;
  cin >> tests_;
  for (int tt_ = 1; tt_ <= tests_; ++tt_) {
    solveTest();
  }

#ifdef GOLIKOV
  cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
      chrono::high_resolution_clock::now()
          - _clock_start).count() << "ms." << endl;
#endif
  return 0;
}