#include <stdio.h>
long T,n,k,i,a[10240];
bool pB();bool pC();

bool pB(){
   if (k>n)return 0;
   if (a[k]==1){
      if (k+4>n)return 0;
      if (a[k+2]!=3)return 0;
      k+=4;return pC();
   }
   if (a[k]==2){k++;return pB();}
return 0;
}
/*bool pC(){
   if (k>n)return 0;
   if (k<=n&&a[k]==2){k++;return 1;}
   if (a[k]==3){if (k+6>n)return 0; k++; pB(); pC();}
   if (a[k]==1){if(k+2>n)return 0; if (a[k+1]!=2)return 0;else {k+=3;return 1;}}
return 0;
}*/
bool pC(){  
  if(k<=n&&a[k]==2){k++;  return 1;}  
  if(k+2<=n&&a[k]==1&&a[k+1]==2&&a[k+2]>0&&a[k+2]<4){k+=3;  return 1;}  
  if(k+6>n)  return 0;  
  if(a[k]!=3)  return 0;  
  ++k;  
  if(pB())  
    return pC();  
  else return 0;  
}

int main(){
    freopen("perle.in","r",stdin);
    freopen("perle.out","w",stdout);
    scanf("%ld\n",&T);
    while(T--){
       scanf("%ld ",&n);for (i=1;i<=n;++i)scanf("%ld",&a[i]);
       if (n==1){printf("1\n");continue;}
       k=1;
       if (pB()&&k>=n)printf("1\n");
       else {//k=1;if (pC()&&k>=n)printf("1\n");
                /* else*/ printf("0\n");
            }
    }
return 0;
}