#include<stdio.h>
#define b 1
#define c 2
int n,i,t;
char a[10001],l;
int ver(int &i,int l)
{for(;;)
  if(l==b) if(a[i]==3) return 0;
	   else  if(a[i]==2) if(n-i>2) {i++;continue;}
			     else return 0;
		  else if(a[i+2]!=3||n-i<4) return 0;
		       else {l=c;i=i+4;}
  else if(a[i]==2) return 1;
       else if(a[i]==1) if(a[i+1]!=2||n-i<2) return 0;
			else  return 1;
	    else if(n-i<=2||a[i+1]==3) return 0;
		  else
		   if(!ver(i,b)||n-i==0) return 0;
		    else i++;}
int main()
{freopen("perle.in","r",stdin);
 freopen("perle.out","w",stdout);
 scanf("%d",&t);
 for(;t;t--){scanf("%d",&n);
 for(i=1;i<=n;i++) scanf("%d",&a[i]);
 if(n==1) printf("1\n");
 else if(n==2) printf("0\n");
      else
 {if(a[1]==2) {l=b;i=2; }
   else if(a[1]==3) {l=c;i=2;}
	   else if(n==3) if(a[2]==2) {printf("1\n");continue;}
			 else {printf("0\n");continue;}
		 else if(a[3]!=3) {printf("0\n");continue;}
		       else {l=b; i=5;}
  for(;;){
  if(l==b) if(a[i]==3) {printf("0\n");break;}
	   else  if(a[i]==2) if(n-i>1) {i++;continue;}
			     else {printf("0\n");break;}
		  else if(a[i+2]!=3||n-i<4) {printf("0\n");break;}
		       else {l=c;i=i+4;}
  else if(a[i]==2) if(n-i==0) {printf("1\n");break;}
		   else {printf("0\n");break;}
       else if(a[i]==1) if(a[i+1]!=2||n-i!=2) {printf("0\n");break;}
			else {printf("1\n"); break;}
	    else if(n-i<=2||a[i+1]==3) {printf("0\n");break;}
		  else
		   if(!ver(i,b)||n-i==0) {printf("0\n");break;}
		    else i++;
	  }
  }
}
 fclose(stdout);
 return 0;}