#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1000 + 20;
const long long inf = 0x3f3f3f3f3f3f3f3f;
struct Point{
    long long x,y;
    Point(long long _x = 0,long long _y = 0):x(_x),y(_y){}
};
long long cross(Point a,Point b){
   return a.x * b.y - a.y * b.x; 
}
struct node{
    long long sum;
    vector<Point>p;
}g[N][N];
long long count(vector<Point>res){
    long long S = 0;
    // cout<<"----------------------------\n";
    for(int i = 0;i < (int)res.size();i ++){
        // cout<<res[i].x<<" "<<res[i].y<<"\n";
        int nex = i + 1 == (int)res.size()?0:i + 1;
        S += cross(res[i],res[nex]);
    }

    // cout<<S<<"\n";
    return S;
}
void solve()
{
	int n;
    cin>>n;
    vector<int>f(2 * n);
    vector<Point>p(2 * n);
    for(int i = 0;i < n;i ++)
        cin>>f[i],f[i + n] = f[i];
    for(int i = 0;i < n;i ++){
        long long x,y;
        cin>>x>>y;
        p[i] = Point(x,y);
        p[i + n] = Point(x,y);
    }
    for(int i = 0;i < 2 * n;i ++)
        for(int j = 0;j < 2 * n;j ++)
            g[i][j].p.clear(),g[i][j].sum = 0;
    for(int i = 0;i < 2 * n;i ++)
        g[i][i].p.push_back(p[i]);
    for(int len = 2;len <= n;len ++){
        for(int i = 0;i < n;i ++){
            if(f[i] == f[i + len - 1]){
                g[i][i + len - 1].sum = 0;
                g[i][i + len - 1].p.push_back(p[i]);
                g[i][i + len - 1].p.push_back(p[i + len - 1]);

                if(g[i][i + len - 2].sum > g[i][i + len - 1].sum)
                    g[i][i + len - 1] = g[i][i + len - 2];
                if(g[i + 1][i + len - 1].sum > g[i][i + len - 1].sum)
                    g[i][i + len - 1] = g[i + 1][i + len - 1];

                int L = i + 1,R = i + len - 2;
                for(int j = L;j <= R;j ++){
                    if(f[j] != f[R])
                        continue;
                    vector<Point>res;
                    res.push_back(p[i]);
                    for(auto v:g[j][R].p)
                        res.push_back(v);
                    res.push_back(p[i + len - 1]);
                    auto sum = count(res) + g[j][R].sum;
                    if(sum >= g[i][i + len - 1].sum){
                        g[i][i + len - 1].sum = sum;
                        g[i][i + len - 1].p.clear();
                        g[i][i + len - 1].p.push_back(p[i]);
                        g[i][i + len - 1].p.push_back(p[i + len - 1]);
                    }
                }
                for(int j = L;j <= R;j ++){
                    if(f[L] != f[j])
                        continue;
                    vector<Point>res;
                    res.push_back(p[i]);
                    for(auto v:g[L][j].p)
                        res.push_back(v);
                    res.push_back(p[i + len - 1]);
                    auto sum = count(res) + g[L][j].sum;
                    if(sum >= g[i][i + len - 1].sum){
                        g[i][i + len - 1].sum = sum;
                        g[i][i + len - 1].p.clear();
                        g[i][i + len - 1].p.push_back(p[i]);
                        g[i][i + len - 1].p.push_back(p[i + len - 1]);
                    }
                }
            } else {
                int L = i,R = i + len - 1;
                for(int j = L;j <= R;j ++){
                    if(f[j] != f[R])
                        continue;
                    if(g[j][R].sum >= g[i][i + len - 1].sum){
                        g[i][i + len - 1] = g[j][R];
                    }
                }
                for(int j = L;j <= R;j ++){
                    if(f[L] != f[j])
                        continue;
                    if(g[L][j].sum >= g[i][i + len - 1].sum){
                        g[i][i + len - 1] = g[L][j];
                    }
                } 
            }
        }
    }
    long long ans = 0;
    for(int i = 0;i < n;i ++)
        ans = max(ans,g[i][i + n - 1].sum);
    cout<<ans<<"\n";
}
signed main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cout<<fixed<<setprecision(12);
	int T=1;
	cin>>T;
	while(T--)
	{
		solve();
	}
}