#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2000 + 200;
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; 
}
long long g[N][N];
long long count(vector<Point>res){
    long long S = 0;
    for(int i = 0;i < (int)res.size();i ++){
        int nex = i + 1 == (int)res.size()?0:i + 1;
        S += cross(res[i],res[nex]);
    }
    assert(S >= 0);
    return llabs(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];
    map<int,vector<int>>M;
    for(int i = 0;i < 2 * n;i ++)
        M[f[i]].push_back(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] = -inf;
    for(int i = 0;i < 2 * n;i ++)
        g[i][i] = 0;
    long long ans = 0;
    vector<int>vis(2 * n);
    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] = max(g[i][i + len - 1],0ll);

                for(int j = i + 1;j <= i + len - 2;j ++){
                    if(vis[j])
                        continue;
                    auto &vec = M[f[j]];
                    auto il = lower_bound(vec.begin(),vec.end(),i + 1);
                    auto ir = lower_bound(vec.begin(),vec.end(),i + len - 1);
                    ir --;
                    vector<Point>res;
                    for(auto it = ir;it != il;it --){
                        res.clear();
                        res.push_back(p[i]);
                        if(*il == *it)
                            res.push_back(p[*il]);
                        else
                            res.push_back(p[*il]),res.push_back(p[*it]);
                        res.push_back(p[i + len - 1]);
                        long long sum = count(res) + g[*il][*it];
                        ans = max(ans,sum);
                        g[i][i + len - 1] = max(g[i][i + len - 1],sum);
                    }

                    for(auto it = il;it != ir;it ++){
                        res.clear();
                        res.push_back(p[i]);
                        if(*ir == *it)
                            res.push_back(p[*ir]);
                        else
                            res.push_back(p[*it]),res.push_back(p[*ir]);
                        res.push_back(p[i + len - 1]);
                        long long sum = count(res) + g[*it][*ir];
                        ans = max(ans,sum);
                        g[i][i + len - 1] = max(g[i][i + len - 1],sum);
                    }
                    ir ++;
                    for(auto it = il;it != ir;it ++){
                        vis[*it] = 1;
                        res.clear();
                        res.push_back(p[i]);
                        res.push_back(p[*it]);
                        res.push_back(p[i + len - 1]);
                        long long sum = count(res) + g[*it][*it];
                        ans = max(ans,sum);
                        g[i][i + len - 1] = max(g[i][i + len - 1],sum);
                    }
                    
                }
                for(int j = i + 1;j <= i + len - 2;j ++)
                    vis[j] = 0;
            }
        }
    }
    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();
	}
}