#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],id[2005];
struct node{
	ll x,y;
}p[500005];
ll f[3][1505][1505];
ll area(int p1,int p2,int p3){
	p1=(p1-1)%n+1;
	p2=(p2-1)%n+1;
	p3=(p3-1)%n+1;
	ll k=(p[p1].x-p[p2].x)*(p[p1].y-p[p3].y)-(p[p1].y-p[p2].y)*(p[p1].x-p[p3].x);
	return k>0?k:-k;
}
inline int read()
{
	int ret=0,ty=1;char ch=getchar();
	while(ch<'0' || ch>'9'){
		if(ch=='-')ty=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9')
	{
		ret=ret*10+ch-'0';
		ch=getchar();
	}
	return ret*ty;
}
int main(){
	scanf("%d",&tt);
	while(tt--){
		n=read();
		for(int i=1;i<=n;++i){
			v[i]=read();
			id[i+n]=id[i]=i;
			v[i+n]=v[i];
		}
		for(int i=1;i<=n;++i){
			p[i].x=read(),p[i].y=read();
		}
		for(int i=1;i<=n;++i)
			for(int j=1;j<=n;++j) f[0][i][j]=f[1][i][j]=f[2][i][j]=-1;
		ll ans=0;
		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[0][i][id[j]]=max(f[0][i][id[j]],0LL);
					for(int k=i+1;k<j;++k){
						ll A=area(i,j,k);
						f[1][id[k]][id[j]]=max(f[1][id[k]][id[j]],f[0][i][id[j]]+A);
						f[2][i][id[k]]=max(f[2][i][id[k]],f[0][i][id[j]]+A);
					}
				}
				if(f[1][i][id[j]]!=-1){
					for(int k=j-1;k>i;--k){
						if(v[k]!=v[i]) continue;
						ll A=area(i,j,k);
						f[0][i][id[k]]=max(f[1][i][id[j]]+A,f[0][i][id[k]]);
						break;
					}
					for(int k=i+1;k<j;++k){
						if(v[k]!=v[j]) continue;
						ll A=area(i,j,k);
						f[0][id[k]][id[j]]=max(f[2][i][id[j]]+A,f[0][id[k]][id[j]]);
						break;
					}
				}
			}
		}
		for(int i=1;i<=n;++i)
			for(int j=1;j<=n;++j){
				ans=max(ans,f[0][i][j]);
				ans=max(ans,f[1][i][j]);
				ans=max(ans,f[2][i][j]);
			}
		printf("%lld\n",ans);
	}
}