#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define rint int
#define endl '\n'
#define uint unsigned long long
void debug(int *a,int n){for(rint i=1;i<=n;i++) cout<<a[i]<<" ";cout<<endl;}
void debug(int *a){for(rint i=1;a[i];i++) cout<<a[i]<<" ";cout<<endl;}
void debug(int x){cout<<"debug: "<<x<<endl;}
int read(){
    int x=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c))x=x*10+c-48,c=getchar();
    return x*f;
}const int N=1010,p=1e9,mod=998244353;

int n,a[N],cnt,b[N],nxt[N][N],pre[N][N];
struct Point{
	int x,y;
	Point operator-(const Point &A)const{return {x-A.x,y-A.y};}
	int   operator^(const Point &A)const{return abs(x*A.y-y*A.x);}
}P[N];
inline Point adjus(int x,int y){
	swap(x,y);
	if(x>n) x-=n;
	if(y<x) y+=n;
	return {x,y};
}

inline int cal(int x,int y,int z,int k)
{
	// puts("cal");
	return ((P[x]-P[y])^(P[x]-P[k]))+((P[z]-P[y])^(P[z]-P[k]));
}
inline int cal(int x,int y,int k)
{
	// puts("cal");
	return ((P[x]-P[y])^(P[x]-P[k]));
}

int dfs(int l,int r);
int bfs(int l,int r);

int f[N][N];
int dfs(int l,int r)
{
	if(f[l][r]!=-1) return f[l][r];
	int res=0;
	// for(rint k=1;k<=cnt;k++)
	// {
	// 	const int i=nxt[l][k],j=pre[r][k];
	// 	if(i<j) res=max(res,dfs(i,j)+cal(l,i,j,r));
	// }
	// for(rint i=l+1;i<r;i++)
	// for(rint j=i+1;j<r;j++)
	// if(a[i]==a[j])
	// 	res=max(res,dfs(i,j)+cal(l,i,j,r));
	for(rint i=l+1;i<r;i++)
		res=max(res,bfs(i,r)+cal(l,i,r));
	return f[l][r]=res;
}
int g[N][N];
int bfs(int l,int r)
{
	if(g[l][r]!=-1) return g[l][r];
	int res=-p*4;
	for(rint i=l+1;i<r;i++)
	if(a[i]==a[l])
		res=max(res,dfs(l,i)+cal(l,i,r));
	return g[l][r]=res;
}

void Work()
{
	n=read(),cnt=0;
	for(rint i=1;i<=n;i++) a[i]=a[i+n]=read(),b[++cnt]=a[i];
	sort(b+1,b+cnt+1);
	cnt=unique(b+1,b+cnt+1)-b-1;
	for(rint i=1;i<=n<<1;i++) a[i]=lower_bound(b+1,b+cnt+1,a[i])-b;
	
	static int c[N];
	for(rint i=1;i<=cnt;i++) c[i]=n*2+1;
	for(rint i=n<<1;i;i--)
	{
		for(rint j=1;j<=cnt;j++) nxt[i][j]=c[j];
		c[a[i]]=i;
	}
	for(rint i=1;i<=cnt;i++) c[i]=0;
	for(rint i=1;i<=n<<1;i++)
	{
		for(rint j=1;j<=cnt;j++) pre[i][j]=c[j];
		c[a[i]]=i;
	}
	
	for(rint i=1;i<=n;i++) P[i]=P[i+n]={read(),read()};
	
	for(rint i=0;i<=n*2;i++)
	for(rint j=0;j<=n*2;j++) f[i][j]=g[i][j]=-1;
	// memset(f,-1,sizeof f);
	
	int ans=0;
	for(rint i=1;i<=n;i++)
	for(rint j=i+1;j<i+n;j++)
	if(a[i]==a[j])
	{
		// cout<<i<<" "<<j<<" "<<dfs(i,j)<<endl;
		ans=max(ans,dfs(i,j));
	}	
	
	for(rint i=1;i<=n;i++)
	for(rint j=i+1;j<i+n;j++)
	if(a[i]==a[j])
		assert(P[i].x==P[adjus(i,j).y].x),
		assert(P[i].y==P[adjus(i,j).y].y),
		assert(P[j].x==P[adjus(i,j).x].x),
		assert(P[j].y==P[adjus(i,j).x].y);
	
	for(rint i=1;i<=n;i++)
	for(rint j=i+1;j<i+n;j++)
	if(a[i]==a[j])
	for(rint k=i+1;k<j;k++)
		ans=max(ans,cal(i,j,k)+dfs(adjus(i,j).x,adjus(i,j).y));
	
	cout<<ans<<endl;
}

signed main()
{
    #ifndef ONLINE_JUDGE
	freopen("1.in", "r", stdin);
	// freopen("1.out", "w", stdout);
	#else
	#endif
    
	// int T=1;
	int T=read();
	while(T--) Work();
	
    return 0;
}