#include<cstdio>
#include<algorithm>
#define M 1005
#define i64 long long
using namespace std;
struct Point{
    long long x,y;
}A[M];
i64 cross(Point a,Point b){
    return a.x*b.y-a.y*b.x;
}
int val[M];
i64 sum[M];
int n;
// i64 Get_val(int L,int R){
//     if(L==R)return 0;
//     // printf("<%d %d>\n",L,R);
//     // puts("B");
//     i64 res=0;
//     if(L<=R){
//         if(L)res=sum[R-1]-sum[L-1]+cross(A[R],A[L]);
//         else res=sum[R-1]+cross(A[R],A[L]);
//     }else{
//         if(R==0)res=sum[n-1]-sum[L-1]+cross(A[R],A[L]);
//         else res=sum[n-1]-sum[L-1]+cross(A[R],A[L])+sum[R-1];
//     }
//     // printf("[%d %d]%lld\n",L,R,res);
//     // puts("E");
//     return res;
// }
int lst[M],Nxt[M][M],Pre[M][M];
i64 dp[M][M];
bool In(int Lx,int Rx,int d){
    if(Lx<=Rx)return Lx<=d&&d<=Rx;
    return d>=Lx||d<=Rx;
}
bool mark[M][M];
i64 Area(Point a,Point b,Point c){
//	printf("%lld %lld %lld %lld\n",cross(a,b),cross(b,c),cross(c,a),cross(a,b)+cross(b,c)+cross(c,a));
	return abs(cross(a,b)+cross(b,c)+cross(c,a));
}
int B[M],sz;
i64 dfs(int L,int R){
//     printf("[%d %d]\n",L,R);
    if(L==R)return 0;
    if(mark[L][R])return dp[L][R];
    mark[L][R]=true;
    i64 res=0;
    int p=(L-1+n)%n;
    while(p!=R){
    	int Lx=p,Rx=Nxt[R][val[p]];
    	if(!In(L,R,Lx)&&!In(L,R,Rx)){
//	        printf("[%d %d]-->[%d %d]\n",L,R,Lx,Rx);
//	    	res=max(res,cross(A[Lx],A[L])+cross(A[R],A[Rx])+dfs(Lx,Rx));
	    	res=max(res,Area(A[L],A[Lx],A[R])+Area(A[R],A[Lx],A[Rx])+dfs(Lx,Rx));
	    }
	    
	    res=max(res,Area(A[L],A[p],A[R]));
    	p=(p-1+n)%n;
	}
	p=(R+1)%n;
    while(p!=L){
//    	printf("p=%d\n",p);
    	int Rx=p,Lx=Pre[L][val[p]];
    	if(!In(L,R,Lx)&&!In(L,R,Rx)){
	    	res=max(res,Area(A[L],A[Lx],A[R])+Area(A[R],A[Lx],A[Rx])+dfs(Lx,Rx));
//	    	res=max(res,cross(A[Lx],A[L])+cross(A[R],A[Rx])+dfs(Lx,Rx));
	    }
    	p=(p+1+n)%n;
	}
    for(int i=0;i<sz;i++){
        int Lx=Pre[L][i],Rx=Nxt[R][i];
        // if(check(Lx,L,R,Rx))continue;
        if(!In(L,R,Lx)&&!In(L,R,Rx)){
//	        printf("[%d %d]-->[%d %d]\n",L,R,Lx,Rx);
	    	res=max(res,Area(A[L],A[Lx],A[R])+Area(A[R],A[Lx],A[Rx])+dfs(Lx,Rx));
//	        res=max(res,cross(A[Lx],A[L])+cross(A[R],A[Rx])+dfs(Lx,Rx));
	    }
//	    Lx=Pre[L][i];Rx=Pre[Lx][i];
//        if(!In(L,R,Lx)&&!In(L,R,Rx)){
//	        res=max(res,cross(A[Lx],A[L])+cross(A[R],A[Rx])+dfs(Lx,Rx));
//        }
//        
//	    Rx=Nxt[R][i];Lx=Nxt[Rx][i];
//        if(!In(L,R,Lx)&&!In(L,R,Rx)){
//	        res=max(res,cross(A[Lx],A[L])+cross(A[R],A[Rx])+dfs(Lx,Rx));
//        }
	    
    }
    for(int Lx=(L+n-1)%n;Lx!=R;Lx=(Lx+n-1)%n){
    	for(int Rx=(R+1)%n;Rx!=Lx;Rx=(Rx+1)%n){
//    		printf("Lx=%d Rx=%d\n",Lx,Rx);
	    	if(val[Lx]==val[Rx])res=max(res,Area(A[L],A[Lx],A[R])+Area(A[R],A[Lx],A[Rx])+dfs(Lx,Rx));
		}
	}
//     printf("dp[%d][%d]=%lld\n",L,R,(long long )dp[L][R]);
    return dp[L][R]=res;
}
int main(){
    int T;
    scanf("%d",&T);
    for(int step=1;step<=T;step++){
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            scanf("%d",&val[i]);
            B[i]=val[i];
        }
        for(int i=0;i<n;i++){
            scanf("%lld%lld",&A[i].x,&A[i].y);
        }
        for(int i=1;i<=n;i++)lst[i]=0;
        for(int i=0;i<n;i++)for(int j=0;j<n;j++)mark[i][j]=false;
        // printf("res=%lld\n",res);
        sort(B,B+n);
        sz=unique(B,B+n)-B;
        for(int i=0;i<n;i++)val[i]=lower_bound(B,B+sz,val[i])-B;
        for(int i=0;i<2*n;i++){
            for(int j=0;j<sz;j++){
                Pre[i%n][j]=lst[j];
            }
            lst[val[i%n]]=i%n;
        }
        for(int i=2*n-1;i>=0;i--){
            for(int j=0;j<sz;j++){
                Nxt[i%n][j]=lst[j];
            }
            lst[val[i%n]]=i%n;
        }
        // for(int i=0;i<n;i++){
        //     i64 val=cross(A[i],A[(i+1)%n]);
        //     if(i)sum[i]=sum[i-1]+val;
        //     else sum[i]=val;
        // }
        // puts("Initok");
        i64 res=0;
        for(int i=0;i<n;i++){
            // printf("i=%d\n",i);
            int Lx=i,Rx=Nxt[i][val[i]];
            if(Lx==Rx)continue;
            // printf("@i=%d\n",i);
            // if(Lx==Rx)continue;
            res=max(res,dfs(Lx,Rx));
            res=max(res,dfs(Rx,Lx));
            // printf("@@i=%d\n",i);
        }
        long long ans=res;
//        for(int i=0;i<n;i++)for(int j=0;j<n;j++)for(int k=0;k<n;k++)if(val[i]==val[j]||val[i]==val[k]||val[j]==val[k])ans=max(ans,Area(A[i],A[j],A[k]));
        printf("%lld\n",ans);

        // printf("%lf\n",res/2.0);
    }
    return 0;
}