#include<stdio.h>
int x[10001],y[10001],n,g,d,e,k,i,j;
int main()
{
	freopen("perle.in","r",stdin),freopen("perle.out","w",stdout),scanf("%d",&n);
	while(n--) {
		scanf("%d",&g);
     	for(k=i=1;i<=g;++i)
            scanf("%d",x+i);
     	if(x[1]==1)
	     	if(g==1)
	            y[1]=4;
	     	else if(g==3&&x[2]==2)
                y[1]=6;
            else if(g>=5)
                y[1]=5;
            else
                k=0;
		else if(x[1]==2)
            if(g==1)
                y[1]=4;
            else if(g>=2)
                y[1]=5;
            else
                k=0;
        else if(x[1]==3)
            if(g==1)
                y[1]=4;
            else if(g>=3)
                y[1]=6;
            else
                k=0;
     	if(!k) {
		 	printf("0\n");
            continue;
		}
		for(d=1,e=2;k&&d<=g;) {
			for(;d<e&&y[d]<4&&k;++d)
			if(y[d]!=x[d])
        		k=0;
            if(k)
        		if(y[d]==4)
			       	y[d]=x[d++];
				else if(y[d]==5)
                    if(x[d]==1) {
                        for(j=e+3;j>=d+4;--j)
                            y[j]=y[j-4];
                        y[d]=1,y[d+1]=4,y[d+2]=3,y[d+3]=4,y[d+4]=6,e+=4;
                    } else if(x[d]==2) {
                        for(j=e;j>=d+1;--j)
                            y[j]=y[j-1];
                        y[d]=2,y[d+1]=5,++e;
                    } else
                        k=0;
                else if(x[d]==1) {
                    for(j=e+1;j>=d+2;--j)
                        y[j]=y[j-2];
                    y[d]=1,y[d+1]=2,y[d+2]=4,e+=2;
                } else if(x[d]==2)
                    y[d++]=2;
                else {
                    for(j=e+1;j>=d+2;--j)
                        y[j]=y[j-2];
                    y[d]=3,y[d+1]=5,y[d+2]=6,e+=2;
                }
            if(e>g+1)
                k=0;
        }
        printf("%d\n",k);
    }
    return 0;
}