#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using pll = pair<LL, LL>;
using pii = pair<int, int>;

LL dis(pii a, pii b){
    LL x = a.first - b.first, y = a.second - b.second;
    return  x * x + y * y;
}
const int N = 5e3 + 5;
LL dp[N][N];
LL dp2[N][N];
pii points[N];
LL area(pii a, pii b, pii c){
    return a.first * b.second + b.first * c.second + c.first * a.second - a.second * b.first - b.second * c.first - a.first * c.second;
}
void testcase(int cs){
    int n;
    cin >> n;

    for(int i = 0; i < n; i++){
        cin >> points[i].first >> points[i].second;
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++)dp[i][j] = dp2[i][j] = 0;
    }

    for(int len = 1; len < n; len++){
        for(int i = 0; i < n; i++){
            dp[i][(i + len) % n] = max(dp[i][(i + len - 1) % n], max(dp[(i + 1) % n][(i + len) % n], dis(points[i], points[(i + len) % n])));
            dp2[i][(i + len) % n] = dp2[(i + 1) % n][(i + len - 1) % n] + area(points[i], points[(i + 1) % n], points[(i + len) % n]);
        }
    }
//    for(int i = 0; i < n; i++){
//        for(int j = 0; j < n; j++){
//            cout << dp[i][j] << ' ';
//        }
//        cout << endl;
//    }


    LL ans = LLONG_MAX;
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            if(dp2[i][j] > 0 && dp2[j][i] > 0){
                ans = min(ans, dp[i][j] + dp[j][i]);

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



}

/*
2
4
1 0
2 0
1 1
0 0
6
10 4
9 7
5 7
4 5
6 4
9 3

*/

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int T;
    cin >> T;
    for(int i = 1; i <= T; i++){
        testcase(i);
    }
    return 0;
}