#include<bits/stdc++.h>
using namespace std;
#define V vector
#define fi first
#define se second
#define pb push_back
#define lb lower_bound
#define all0(x) (x).begin(), (x).end()
#define all1(x) (x).begin() + 1, (x).end()
typedef pair<int, int> pi;
typedef long long LL;

LL det(pi a, pi b) {
    return 1LL * a.fi * b.se - a.se * b.fi;
}

void solve() {
    int n; cin >> n;
    V<int> f(n * 2);
    V<int> uni(1);
    for(int i = 0; i < n; i++) cin >> f[i], f[i + n] = f[i], uni.pb(f[i]);
    sort(all1(uni));
    uni.erase(unique(all1(uni)), uni.end());
    for(int i = 0; i < 2 * n; i++) f[i] = lb(all1(uni), f[i]) - uni.begin();

    V<pi> a(n * 2);
    for(int i = 0; i < n; i++) {
        cin >> a[i].fi >> a[i].se;
        a[i + n] = a[i];
    }
    auto cal = [&](pi a, pi b, pi c, pi d) {
        return det(a, c) + det(c, d) + det(d, b) + det(b, a);
    };
    LL ans = 0;
    V<V<LL>> dp(n * 2, V<LL>(n * 2));
    V<int> ocur(n + 1, -1);
    for(int len = 1; len <= n; len++) {
        for(int l = 0; l < 2 * n - len + 1; l++) {
            int r = l + len - 1;
            if(f[l] != f[r]) continue;
            for(int i = l + 1; i < r; i++) {
                if(ocur[f[i]] == -1) {
                    ocur[f[i]] = i;
                }
            }

            for(int i = l + 1; i < r; i++) {
                dp[l][r] = max(dp[l][r], dp[ocur[f[i]]][i] + cal(a[l], a[r], a[ocur[f[i]]], a[i]));
            }

            for(int i = l + 1; i < r; i++) {
                ocur[f[i]] = -1;
            }
            ans = max(ans, dp[l][r]);
        }
    }
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int t = 1;
    cin >> t;
    while(t--) solve();
}