#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 3004
ll t, n, minn = 0;
long double maxx = 0;
int last[maxn][maxn], nex[maxn][maxn];
long double ans;
unordered_map<ll, int> f;
int tot = 0;
struct point
{
    ll x, y, f;
} a[maxn];

ll mul(point a, point b)
{
    return abs(a.x * b.y - a.y * b.x);
}

void dfs(int v, int u, long double ans)
{
    int min1 = 0, max1 = INT_MAX;

    if (u == v)
    {
        maxx = max(abs(ans), maxx);
        return;
    }

    else if (u == v + 1)
    {
        maxx = max(abs(ans + mul(a[v], a[u])), maxx);
        return;
    }

    for (int i = v + 1; i < u; i++)
    {
        if (last[u][a[i].f] >= min1)
        {
            min1 = max(last[u][a[i].f], min1);
            dfs(i, last[u][a[i].f], ans + mul(a[v], a[i]) + mul(a[last[u][a[i].f]], a[u]));
        }
    }

    for (int i = u - 1; i >= v + 1; i--)
    {
        if (nex[v][a[i].f] <= max1)
        {
            max1 = min(nex[v][a[i].f], max1);
            if (i != last[u][a[i].f]) // 上面的一层搜索已经搜过了
                dfs(i, nex[v][a[i].f], ans + mul(a[v], a[nex[v][a[i].f]]) + mul(a[i], a[u]));
        }
    }

    return;
}
void solve(int x)
{
    int v = x + 1, u;
    ll maxi = 0;
    for (int i = n + x; i >= x + 3 && i >= minn; i--)
    {
        if (a[i].f == a[v].f)
        {
            maxi = max((ll)i, maxi);
            dfs(v, i, mul(a[i], a[v]));
        }
    }
    minn = max(minn, maxi);
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> t;
    while (t--)
    {
        cin >> n;
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i].f;
            a[i + n].f = a[i].f;
            if (!f[a[i].f])
            {
                f[a[i].f] = ++tot;
            }
        }

        for (int i = 1; i <= n; i++)
        {
            cin >> a[i].x >> a[i].y;
            a[i + n].x = a[i].x;
            a[i + n].y = a[i].y;
            int x = f[a[i].f];
            a[i].f = a[i + n].f = x;
        }

        memset(last[1], 0, sizeof(last[1]));

        memset(nex[2 * n - 1], 0, sizeof(nex[2 * n - 1]));

        for (int i = 2; i < 2 * n; i++)
        {
            for (int j = 1; j <= tot; j++)
            {
                if (a[i - 1].f == j)
                    last[i][j] = i - 1;
                else
                    last[i][j] = last[i - 1][j];
            }
        }

        for (int i = 2 * n - 2; i >= 1; i--)
        {
            for (int j = 1; j <= tot; j++)
            {
                if (a[i + 1].f == j)
                    nex[i][j] = i + 1;
                else
                    nex[i][j] = nex[i + 1][j];
            }
        }

        for (int i = 0; i < n; i++)
        {
            solve(i);
        }

        cout << (ll)(maxx + 0.5) << endl;
        maxx = 0;
        minn = 0;
        tot = 0;
        f.clear();
    }
}