#include<bits/stdc++.h>
using namespace std;
inline int read()
{
	int sum=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f*=-1;ch=getchar();}
	while(isdigit(ch)){sum=sum*10+ch-48;ch=getchar();}
	return sum*f;
}
int f[1005];
int dp[1005][1005];
int x[1005],y[1005];
vector<int> V[505];
map<int,int> mp;
inline int cvec(int a,int b)
{
	return (x[a]+x[b])*(y[b]-y[a]);
}
inline void calc(int L,int R,int l,int r)
{
	dp[L][R]=max(dp[L][R],dp[l][r]+cvec(L,l)+cvec(r,R));
}
inline void solve()
{
	mp.clear();
	int n;
	n=read();
	for(int i=1;i<=n;i++) f[i]=read();
	
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		if(mp.count(f[i])) f[i]=mp[f[i]];
		else
		{
			mp[f[i]]=++cnt;
			f[i]=cnt;
		}
	}
	
	for(int i=1;i<=n;i++) x[i]=read(),y[i]=read();
	for(int i=n+1;i<=n*2;i++) f[i]=f[i-n],x[i]=x[i-n],y[i]=y[i-n];
	int ans=0;
	for(int len=1;len<=n;len++)
		for(int l=1;l<=n;l++)
		{
			int r=l+len-1;
			
			if(f[l]!=f[r]) continue;
			dp[l][r]=cvec(l,r);
			
			for(int k=l+1;k<r;k++)V[f[k]].push_back(k);
			for(int g=1;g<=cnt;g++)
			{
				if(V[g].size()==0) continue;
				for(int j=0;j<V[g].size();j++) calc(l,r,V[g][0],V[g][j]);
				for(int j=1;j<V[g].size();j++) calc(l,r,V[g][j],V[g].back());
			}
			for(int g=1;g<=cnt;g++) V[g].clear();
			
			ans=max(ans,dp[l][r]+cvec(r,l));
		}
	cout<<ans<<endl;
}
signed main()
{
	int T;
	T=read();
	while(T--) solve(); 
	return 0;
}