#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1005;
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];
struct node{
	int l,r;
};
queue<node> q;
int T,n,cnt,f[N],L[N][N],R[N][N],P[N];
__int128 F[N][N];
ll ans;
bool vis[N][N];
unordered_map<int,int> mp; 

void BFS(int sl,int sr)
{
	for(int i=sl;i<=sr;i++) for(int j=i;j<=sr;j++) F[i][j]=-INF,vis[i][j]=false;
	F[sl][sr]=p[sr]^p[sl];
	q.push({sl,sr});vis[sl][sr]=true;
	node now;int lst,l,r;
	while(!q.empty())
	{
		now=q.front();q.pop();lst=0;
		l=now.l;r=now.r;
		ans=max(ans,(ll)(F[l][r]+(p[l]^p[r])));
		for(int i=l+1;i<r;i++)
		{
			if(L[r][f[i]]<i||L[r][f[i]]<=lst) continue;
			lst=L[r][f[i]];
			F[i][lst]=max(F[i][lst],F[l][r]+(p[l]^p[i])+(p[lst]^p[r]));
			if(!vis[i][lst]) q.push({i,lst}),vis[i][lst]=true;
		}
	}
	return;
}
int g(int x)
{
	if(mp.find(x)==mp.end()) mp[x]=++cnt;
	return mp[x];
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while(T--)
	{
		cin>>n;cnt=0;ans=-INF;
		for(int i=1;i<=n;i++) cin>>f[i],f[i]=g(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;
		}
		for(int i=1;i<=cnt;i++) P[i]=n*2+1;
		for(int i=n*2;i>=1;i--)
		{
			for(int j=1;j<=cnt;j++) R[i][j]=P[j];
			P[f[i]]=i;
		}
		for(int i=1;i<=n;i++)
		{
			if(R[i][f[i]]>=n+i) continue;
			BFS(i,R[i][f[i]]);
			if(R[i][f[i]]<=n) BFS(R[i][f[i]],i+n);
			else BFS(R[i][f[i]]-n,i);
		}
		cout<<ans<<"\n";
		mp.clear();
	}
	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
3
1 2 3
0 0
1 0
0 1
3
1 1 1
0 0
1 0
0 1
*/