#include<fstream>
using namespace std;
int a[10001];
int tryc(int st, int dr);
int tryb(int st, int dr);
int trya(int st, int dr);
int trybc(int st, int dr){
  if(st>dr) return 0;
  int i;
  for(i=dr-st;i>=0;i--){
    if(tryb(st,st+i))
      if(tryc(st+i+1,dr))
        return 1;
  }
  return 0;
}
int trya(int st, int dr){
 if(st>dr)  return 0;
 if(st!=dr)  return 0;
 if(a[st]<1||a[dr]>3)  return 0;
 return 1;
}
int tryb(int st, int dr){
  if(st>dr)   return 0;
  if(a[st]!=1&&a[st]!=2)  return 0;
  if(a[st]==2) return tryb(st+1,dr);
  if(a[st]==1) return (trya(st+1,st+1)&&(st+2<=dr&&a[st+2]==3)&&trya(st+3,st+3)&&tryc(st+4,dr));
}
int tryc(int st, int dr){
  if(st>dr) return 0;
  if(st==dr){
    if(a[st]==2)  return 1;
    return 0;
  }
  if(a[st]!=3&&a[st]!=1)  return 0;
  if(a[st]==3){
    return trybc(st+1,dr);
  }
  if(a[st]==1){
    if(st+1>dr) return 0;
    if(a[st+1]!=2) return 0;
    return trya(st+2,dr);
  }
}
int main(){
  int n,i,l, j, r;
  ifstream f("perle.in");
  ofstream g("perle.out");
  f>>n;
  for(i=0;i<n;i++){
    f>>l;
    for(j=0;j<l;j++)
      f>>a[j];
    r=trya(0,l-1);
    if(!r) r=r||tryb(0,l-1);
    if(!r) r=r||tryc(0,l-1);
    g<<r<<'\n';
  }
  g.close();
  f.close();
  return 0;
}