#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 998244353;
inline void cmax(int &x, const int &y) {
    if (x < y) x = y;
}
struct Point {
    int x, y;
    friend Point operator-(const Point&x, const Point&y) {
        return {x.x - y.x, x.y - y.y};
    }
    friend int operator^(const Point&x, const Point&y) {
        return x.x * y.y - y.x * x.y;
    }
};

inline int Area(const Point &x, const Point&y, const Point&z) {
    Point A = y - x;
    Point B = z - x;
    return abs(A ^ B);
}

inline void Solve() {
    int n, k; cin >> n;
    vector<int> a, tv; a.reserve(n * 2);
    for (int i = 1, x; i <= n; i++) cin >> x, a.push_back(x), tv.push_back(x);
    sort(tv.begin(), tv.end());
    tv.erase(unique(tv.begin(), tv.end()), tv.end());
    for (int i = 0; i < n; i++) a[i] = lower_bound(tv.begin(), tv.end(), a[i]) - tv.begin();
    vector<vector<int>>lst(2 * n, vector<int>(2 * n, -1));
    for (int i = 0; i < n; i++) a.push_back(a[i]);

    for (int i = 0; i < 2 * n; i++) {
        for (int j = 0; j < tv.size(); j++) {
            if (j == a[i]) lst[i][a[i]] = i;
            else lst[i][j] = ((i == 0) ? -1 : lst[i - 1][j]);
        }
    }
    vector<Point> v; v.reserve(n * 2);
    for (int i = 0, x, y; i < n; i++) {
        cin >> x >> y;
        v.push_back({x, y});
    }
    for (int i = 0; i < n; i++) v.push_back(v[i]);
    vector<vector<int>> f(2 * n + 5, vector<int>(2 * n + 5, -1));
    int ans = 0;
    for (int len = 1; len <= n; len++) {
        for (int l = 0; l + len - 1 < 2 * n; l++) {
            int r = l + len - 1;
            if (a[l] != a[r]) continue;
            if (len <= 2) {
                f[l][r] = 0;
                continue;
            }
            if (l >= n) continue;
            // cout << l << " & " << r << endl;
            for (int k = l + 1; k < r; k++) {
                int pl = k;
                int pr = lst[r - 1][a[pl]];
                // cout << pl << " : " << pr << f[pl][pr] << endl;
                if (pr < pl || f[pl][pr] == -1) continue;
                cmax(f[l][r], f[pl][pr] + Area(v[l], v[r], v[pr]) + Area(v[l], v[pr], v[pl]));
                // cout << "\t" << f[l][r] << " " << pl << " " <<  pr << ": " << f[pl][pr] << " " <<  Area(v[l], v[r], v[pr]) << " "<<  Area(v[l], v[pr], v[pl])<<endl;
                cmax(ans, f[l][r]);
            }
        }
    }
    cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--) Solve();
    return 0;
}


/*
1
10
3 3 2 4 0 2 3 2 4 1
7 16
0 0
75 31
80 43
80 55
76 61
63 64
45 51
28 37
13 23
*/