#include <cstdio>
#include <cstring>
#include <vector>
#include <cassert>
#include <algorithm>

const int N = 505;
int tt, n, col_cnt, a[N], col[N];
long long dp[N][N];
std::vector<int> pos[N];
bool vis[N];

struct point {
    int x, y;
    point(int x = 0, int y = 0) {
        this->x = x;
        this->y = y;
    }
} p[N];

point operator-(point a, point b) {
    return point(a.x - b.x, a.y - b.y);
}

long long cross(point a, point b) {
    return (long long)a.x * b.y - a.y * b.x;
}

long long area(point a, point b, point c, point d) {
    return cross(a, b) + cross(b, c) + cross(c, d) + cross(d, a);
    //return cross(a - b, c - b) + cross(b - c, d - c) + cross(c - d, a - d) + cross(d - a, b - a);
}

int dist(int l, int r) {
    if (l < r) return r - l;
    return r + n - l;
}

void update(int l, int r, int i, int j) {
    assert(a[i] == a[j]);
    dp[l][r] = std::max(dp[l][r], area(p[l], p[i], p[j], p[r]) + dp[i][j]);
}

int main() {
    scanf("%d", &tt);
    while (tt--) {
        scanf("%d", &n);
        for (int i = 0; i < n; ++i) {
            scanf("%d", a + i);
            col[i] = a[i];
            pos[i].clear();
        }
        std::sort(col, col + n);
        col_cnt = std::unique(col, col + n) - col;
        for (int i = 0; i < n; ++i) {
            a[i] = std::lower_bound(col, col + col_cnt, a[i]) - col;
            //printf("%d ", a[i]);
            pos[a[i]].push_back(i);
        }
        //printf("\n");
        for (int i = 0; i < n; ++i) {
            scanf("%d%d", &p[i].x, &p[i].y);
            dp[i][i] = 0;
        }
        long long ans = 0;
        for (int len = 1; len < n; ++len) {
            int r = len;
            for (int l = 0; l < n; ++l, ++r) {
                if (r == n) r = 0;
                if (a[l] != a[r]) continue;
                dp[l][r] = 0;
                for (int i = l + 1;; ++i) {
                    if (i == n) i = 0;
                    if (i == r) break;
                    dp[l][r] = std::max(dp[l][r], cross(p[r] - p[i], p[l] - p[i]));
                }
                /*
                for (int i = l + 1;; ++i) {
                    if (i == n) i = 0;
                    if (i == r) break;
                    for (int j = i + 1;; ++j) {
                        if (j == n) j = 0;
                        if (j == r) break;
                        if (a[i] == a[j]) dp[l][r] = std::max(dp[l][r], area(p[l], p[i], p[j], p[r]) + dp[i][j]);
                    }
                }
                */
                int cur_col = -1, cur_pos = -1, cur_dist = n;
                memset(vis, 0, col_cnt);
                for (int i = l + 1;; ++i) {
                    if (i == n) i = 0;
                    if (i == r) break;
                    if (vis[a[i]]) {
                        if (cur_col == a[i]) update(l, r, i, cur_pos);
                    } else {
                        vis[a[i]] = true;
                        for (int j = 0; j < (int)pos[a[i]].size(); ++j) {
                            int p = pos[a[i]][j];
                            if (p != r && p != l && p != i && dist(i, r) == dist(i, p) + dist(p, r)) {
                                update(l, r, i, p);
                                if (cur_dist > dist(p, r)) {
                                    cur_col = a[i];
                                    cur_pos = p;
                                    cur_dist = dist(p, r);
                                }
                            }
                        }
                    }
                }
                ans = std::max(ans, dp[l][r]);
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}