#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1005;
const ll INF = 0x3f3f3f3f3f3f3f3f;
struct point {
    int x, y;
    ll operator^(const point& t) const {
        return 1ll * x * t.y - 1ll * y * t.x;
    }
} p[N];
struct node {
    int l, r;
};
queue<node> q;
int T, n, cnt, f[N], L[N][N], R[N][N], P[N];
__int128 F[N][N];
ll ans;
bool vis[N][N];
unordered_map<int, int> mp;

void BFS(int sl, int sr) {
    for (int i = sl; i <= sr; i++)
        for (int j = i; j <= sr; j++) F[i][j] = -INF, vis[i][j] = false;
    F[sl][sr] = p[sr] ^ p[sl];
    q.push({sl, sr});
    vis[sl][sr] = true;
    node now;
    int lst, l, r;
    while (!q.empty()) {
        now = q.front();
        q.pop();
        lst = 0;
        l = now.l;
        r = now.r;
        ans = max(ans, (ll)(F[l][r] + (p[l] ^ p[r])));
        for (int i = l + 1; i < r; i++) {
            if (L[r][f[i]] < i || L[r][f[i]] <= lst || L[i][f[i]] > l) continue;
            lst = L[r][f[i]];
            F[i][lst] = max(F[i][lst], F[l][r] + (p[l] ^ p[i]) + (p[lst] ^ p[r]));
            if (!vis[i][lst]) q.push({i, lst}), vis[i][lst] = true;
        }
    }
    return;
}
int g(int x) {
    if (mp.find(x) == mp.end()) mp[x] = ++cnt;
    return mp[x];
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> T;
    while (T--) {
        cin >> n;
        cnt = 0;
        ans = -INF;
        for (int i = 1; i <= n; i++) cin >> f[i], f[i] = g(f[i]), f[n + i] = f[i];
        for (int i = 1; i <= n; i++) cin >> p[i].x >> p[i].y, p[n + i] = p[i];
        for (int i = 1; i <= cnt; i++) P[i] = 0;
        for (int i = 1; i <= n * 2; i++) {
            for (int j = 1; j <= cnt; j++) L[i][j] = P[j];
            P[f[i]] = i;
        }
        for (int i = 1; i <= cnt; i++) P[i] = n * 2 + 1;
        for (int i = n * 2; i >= 1; i--) {
            for (int j = 1; j <= cnt; j++) R[i][j] = P[j];
            P[f[i]] = i;
        }
        for (int i = 1; i <= n; i++) {
            // if (R[i][f[i]] >= n + i) continue;
            if (R[i][f[i]] <= n) BFS(R[i][f[i]], i + n);
            for (int j = i + 1; j < i + n; ++j) {
                if (f[j] == f[i + n]) BFS(j, i + n);
            };
            // else BFS(R[i][f[i]] - n, i);
        }
        if (ans == -INF)
            cout << "0\n";
        else
            cout << ans << "\n";
        mp.clear();
    }
    return 0;
}
/*
3
8
2 4 2 4 3 4 5 3
2 3
0 6
-3 3
-3 0
-2 -3
1 -5
3 -3
4 0
3
1 2 3
0 0
1 0
0 1
3
1 1 1
0 0
1 0
0 1
*/