#include<fstream.h>
ifstream f("perle.in");
ofstream g("perle.out");
int n,v,t;
int s[10005];
int B(int);
int C(int);
int main()
{ int q,i;
  f>>t;
  for(q=0;q<t;q++)
	  { f>>n;
		for(i=0;i<n;i++) f>>s[i];
	    if(n==1) g<<1<<'\n';
		    else if(n==2) g<<0<<'\n';
				    else if(n==3) if(s[0]=='1'&&s[1]=='2') g<<1<<'\n';
								    else g<<0<<'\n';
						    else { if(s[0]=='1') v=B(0);
									    else if(s[0]=='2') v=B(0);
											    else v=C(0);
								   if(v==n) g<<1<<'\n';
									  else g<<0<<'\n';
							     }
	  }
  f.close(); g.close();
  return 0;
}

int B(int i)
{ //g<<i<<'*';
  if(i>=n) return -1;
  if(s[i]==3) return -1;
  if(s[i]==2) return B(i+1);
  if(s[i+2]!=3) return -1;
  if(s[i+3]<=0||s[i+3]>=4) return -1;
  return C(i+4);
}


int C(int i)
{ //g<<i<<'#';
  if(s[i]==2) return i+1;
  if(s[i]==1) if(s[i+1]==2) return i+3;
					else return -1;
  return C(B(i+1));
}