#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll N=1003,INF=1e18;
ll n,b[N],f[N][N],g[N][N];
array<ll,2> a[N];
void Max(ll &x,ll y){if(x<y)x=y;}
ll Cro(ll x,ll y){return a[x][0]*a[y][1]-a[x][1]*a[y][0];}
void Solve()
{
	cin>>n;ll ans=0;
	for(int i=1;i<=n;i++)cin>>b[i],b[i+n]=b[i];
	for(int i=1;i<=n;i++)cin>>a[i][0]>>a[i][1],a[i+n]=a[i];
	for(int i=1;i<=2*n;i++)for(int j=1;j<=2*n;j++)f[i][j]=g[i][j]=-INF;
	for(int i=1;i<=2*n;i++)for(int j=i+1;j<=2*n;j++)if(b[i]==b[j])f[i][j]=Cro(i,j);
	for(int i=1;i<=2*n;i++)f[i][i]=0;
	for(int len=1;len<n;len++)for(int l=1,r=len;r<=2*n;l++,r++)
	{
		Max(ans,f[l][r]+Cro(r,l));
		for(int i=1;i<l;i++)Max(g[i][r],f[l][r]+Cro(i,l));
		for(int i=r+1;i<=2*n;i++)if(b[i]==b[l])Max(f[l][i],g[l][r]+Cro(r,i));
	}
	cout<<ans<<endl;
}
int main()
{
	int T;cin>>T;
	while(T--)Solve();
	return 0;
}