#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#include<queue>
#include<map>
#define ll long long
using namespace std;
int tt,n,v[2005];
struct node{
	ll x,y;
}p[500005];
ll f[1005][1005][3];
node ms(node a,node b){
	node c;
	c.x=a.x-b.x,c.y=a.y-b.y;
	return c;
}
ll cross(node a,node b){
	return abs(a.x*b.y-a.y*b.x);
}
ll area(int p1,int p2,int p3){
	p1=(p1-1)%n+1;
	p2=(p2-1)%n+1;
	p3=(p3-1)%n+1;
	return cross(ms(p[p1],p[p2]),ms(p[p1],p[p3]));
}
int id(int i){
	return i=(i-1)%n+1;
}
int main(){
	scanf("%d",&tt);
	while(tt--){
		scanf("%d",&n);
		for(int i=1;i<=n;++i) scanf("%d",&v[i]),v[i+n]=v[i];
		for(int i=1;i<=n;++i){
			scanf("%lld%lld",&p[i].x,&p[i].y);
		}
		for(int i=1;i<=n;++i)
			for(int j=1;j<=n;++j) f[i][j][0]=f[i][j][1]=f[i][j][2]=-1;
		for(int l=n-1;l>=1;--l){
			for(int i=1;i<=n;++i){
				int j=i+l;
				if(v[i]==v[j]) f[i][id(j)][0]=max(f[i][id(j)][0],0LL);
				for(int k=i+1;k<j;++k){
					if(f[i][id(j)][0]!=-1) f[id(k)][id(j)][1]=max(f[id(k)][id(j)][1],f[i][id(k)][0]+area(i,j,k));
					if(f[i][id(j)][0]!=-1) f[i][id(k)][2]=max(f[i][id(k)][2],f[i][id(j)][0]+area(i,j,k));
					if(f[i][id(j)][1]!=-1&&v[k]==v[i]) f[i][id(k)][0]=max(f[i][id(k)][0],f[i][id(j)][1]+area(i,j,k));
					if(f[i][id(j)][2]!=-1&&v[k]==v[j]) f[id(k)][id(j)][0]=max(f[id(k)][id(j)][0],f[i][id(j)][2]+area(i,j,k));
				}
			}
		}
		ll ans=0;
		for(int i=1;i<=n;++i)
			for(int j=1;j<=n;++j){
				ans=max(ans,f[i][j][0]);
				ans=max(ans,f[i][j][1]);
				ans=max(ans,f[i][j][2]);
			}
		printf("%lld\n",ans);
	}
}