#include <iostream>
#include <vector>
#include <array>
#include <queue>
#include <deque>
#include <algorithm>
using namespace std;

const int N = 1e3 + 5;
using point = pair<int, int>;
point a[N];
int n, m, f[N], g[N], nxt[N][N];
long long ans, dp[N][N];
int tot, vis[N];
vector<int> node[N];
point vec(point a, point b)
{
    point res;
    res.first = b.first - a.first;
    res.second = b.second - a.second;
    return res;
}
long long cross(point a, point b)
{
    long long ret = 1ll * a.first * b.second - 
        1ll * a.second * b.first;
    return abs(ret);
}

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> f[i], g[i] = f[i];
    for (int i = 1; i <= n; i++) cin >> a[i].first >> a[i].second, a[i + n] = a[i];
    sort(g + 1, g + n + 1);
    m = unique(g + 1, g + n + 1) - g - 1;
    for (int i = 1; i <= n; i++)
        f[i] = f[i + n] = lower_bound(g + 1, g + m + 1, f[i]) - g;
    for (int i = 1; i <= n * 2; i++) node[f[i]].push_back(i);

    for (int i = 1; i <= m; i++)
    {
        nxt[i][n * 2 + 1] = n * 3 + 1;
        for (int j = n * 2; j >= 1; j--)
        {
            if (f[j] == i) nxt[i][j] = j;
            else nxt[i][j] = nxt[i][j + 1];
        }
    }

    for (int i = 1; i <= n * 2; i++)
        for (int j = i + 1; j <= n * 2; j++)
            dp[i][j] = -1e18;
    for (int i = 1; i < n * 2; i++)
        if (f[i] == f[i + 1])
            dp[i][i + 1] = 0;

    ans = tot = 0;
    for (int r = 1; r <= n * 2; r++)
    {
        for (int l = r; l >= 1 and l > r - n; l--)
        {
            tot += 1;
            if (dp[l][r] < 0) continue;
            ans = max(ans, dp[l][r]);
            for (int x = l - 1; x >= 1 and x > r - n; x--)
            {
                if (vis[x] == tot) continue;
                vis[x] = tot;
                for (int c = 1, y = nxt[f[x]][r + 1]; c <= 16 and y < x + n; c += 1, y = nxt[f[x]][y + 1])
                    dp[x][y] = max(dp[x][y], cross(vec(a[x], a[y]), vec(a[x], a[l])) + cross(vec(a[y], a[r]), vec(a[l], a[r])) + dp[l][r]);
            }
        }
    }
    cout << ans << '\n';

    for (int i = 1; i <= m; i++) node[i].clear(), vis[i] = 0;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;
    while (t--) solve();
}