#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 3004
ll t, n, minn = 0;
ll maxx = 0;
int last[maxn][maxn], nex[maxn][maxn];
bool flag[maxn][maxn];
ll Ans[maxn][maxn];

unordered_map<ll, int> f;
int tot = 0;
struct point
{
    ll x, y, f;
} a[maxn];

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

ll dfs(int v, int u)
{
   
    if (flag[v % n][u % n]){
        return Ans[v % n][u % n];
    }
    if (u == v)
    {
        return 0;
    }
    else if (u == v + 1)
    {
        flag[v % n][u % n] = 1;
        Ans[v % n][u % n] = mul(a[v], a[u]);
        return Ans[v % n][u % n];
    }

    ll ans = LLONG_MIN;
    int min1 = 0, max1 = INT_MAX;

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

    for (int i = u - 1; i >= v + 1; i--)
    {
        if (nex[v][a[i].f] <= max1)
        {
            max1 = min(nex[v][a[i].f], max1);
            ans = max(dfs(nex[v][a[i].f], i) + mul(a[v], a[nex[v][a[i].f]]) + mul(a[i], a[u]), ans);
        }
    }
    
    flag[v % n][u % n] = 1;
    Ans[v % n][u % n] = ans;
   
    return ans;
}
void solve(int x)
{
    int v = x + 1;
    for (int i = n + x; i >= x + 3; i--)
    {
        if (a[i].f == a[v].f)
        {
            maxx = max(abs(dfs(v, i) + mul(a[i], a[v])), maxx);
        }
    }
    return ;
}
int main()
{
    freopen("text.in", "r", stdin);
    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 << maxx << endl;

        maxx = 0;
        minn = 0;
        tot = 0;
        f.clear();

        for (int i = 0; i <n; i++)
        {
            for (int j = 0; j <n; j++)
            {
                flag[i][j] = 0;
            }
        }
    }
}