#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1005,IINF=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
struct point{
	int x,y;
	ll operator ^ (const point &t) const{
		return 1ll*x*t.y-1ll*y*t.x;
	}
}p[N];
int T,n,cnt,mp[N],f[N],L[N][N],R[N][N],P[N];
ll F[N][N];
ll ans;
bool vis[N][N];
void clear(int sl,int sr)
{
	for(int i=sl;i<=sr;i++) F[i][i]=0;
	for(int i=sl;i<=sr;i++) for(int j=i+1;j<=sr;j++) F[i][j]=-INF;
	return;
}
void Dfs(int l,int r)
{
	if(F[l][r]!=-INF) return;
	if(l==r) return;
	int lst=0;F[l][r]=p[l]^p[r];
	for(int i=l+1;i<r;i++)
	{
//		if(L[r][f[i]]<=lst) continue;
		lst=L[r][f[i]];
		Dfs(i,lst);
		F[l][r]=max(F[l][r],F[i][lst]+(p[l]^p[i])+(p[lst]^p[r]));
	}
	ans=max(ans,F[l][r]+(p[r]^p[l]));
	return;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--)
	{
		cin>>n;ans=-INF;
		for(int i=1;i<=n;i++) cin>>f[i],mp[i]=f[i];
		sort(mp+1,mp+n+1);
		cnt=unique(mp+1,mp+n+1)-mp-1;
		for(int i=1;i<=n;i++) f[i]=lower_bound(mp+1,mp+n+1,f[i])-mp,f[n+i]=f[i];
		for(int i=1;i<=n;i++) cin>>p[i].x>>p[i].y,p[n+i]=p[i];
		for(int i=1;i<=cnt;i++) P[i]=0;
		for(int i=1;i<=n*2;i++)
		{
			for(int j=1;j<=cnt;j++) L[i][j]=P[j];
			P[f[i]]=i;
		}
		clear(1,n*2);
		for(int i=1;i<=n;i++)
		{
			for(int j=i;j<n+i;j++)
			{
				if(f[i]==f[j]) Dfs(i,j);
			}
		}
		if(ans==-INF) cout<<"0\n";
		else cout<<ans<<"\n";
	}
	return 0;
}
/*
3
8
2 4 2 4 3 4 5 3
2 3
0 6
-3 3
-3 0
-2 -3
1 -5
3 -3
4 0
8
2 4 2 4 3 4 5 3
2 3
0 6
-3 3
-3 0
-2 -3
1 -5
3 -3
4 0
8
2 4 2 4 3 4 5 3
2 3
0 6
-3 3
-3 0
-2 -3
1 -5
3 -3
4 0
*/