#include <fstream>
using namespace std;
fstream in,out;
char A[10001],B[10001];
int i,j,k;
int n,l;
int ok;
int s;
int x;

void functia_mea()
  {
  x=j;
  while(x>i)
    {
    B[x+s]=B[x];
    x--;
    }
  }


int main()
{
in.open("perle.in",ios::in);
out.open("perle.out",ios::out);
in>>n;
for(k=1;k<=n;k++)
  {
  in>>l;
  if(l==1)
    {
    in>>A[1];
    out<<"1"<<endl;
    }
  else if(l==2)
    {
    in>>A[1]>>A[2];
    out<<"0"<<endl;
    }
  else
    {
    ok=1;
    for(i=1;i<=l;i++)
      in>>A[i];

    if((A[1]=='3') || (A[1]=='1' && A[2]=='2' && l==3))
      B[1]='C';
    else if((A[1]=='2') || (A[1]=='1'))
      B[1]='B';
    else ok=0;

    if(ok==0) out<<"0"<<endl;
    else
      {
      j=1;
      for(i=1;i<=l;i++)
	{
	if(B[i]=='B')
	  {
	  if(A[i]=='2')
	    {
	    B[i]='2';
	    s=1;
	    functia_mea();
	    j++;
	    B[i+1]='B';
	    }
	  else if(A[i]=='1' && A[i+2]=='3')
	    {
	    B[i]='1';
	    s=4;
	    functia_mea();
	    j=j+4;
	    B[i+1]=A[i+1];
	    B[i+2]='3';
	    B[i+3]=A[i+3];
	    B[i+4]='C';
	    }
	  else
	    {
	    ok=0;
	    break;
	    }
	  }
	else if(B[i]=='C')
	  {
	  if(A[i]=='2')
	    B[i]='2';
	  else if(A[i]=='3')
	    {
	    B[i]='3';
	    s=2;
	    functia_mea();
	    j=j+2;
	    B[i+1]='B';
	    B[i+2]='C';
	    }
	  else if(A[i]=='1' && A[i+1]=='2')
	    {
	    B[i]='1';
	    s=2;
	    functia_mea();
	    j=j+2;
	    B[i+1]='2';
	    B[i+2]=A[i+2];
	    }
	  else
	    {
	    ok=0;
	    break;
	    }
	  }
	else if(A[i] != B[i])
	  {
	  ok=0;
	  break;
	  }
	}//Inchide for de i
      if(j != l) ok=0;
      out<<ok<<endl;
      }//Inchide else
    }//Inchide else
  }//Inchide for de k
in.close();
out.close();
return 0;
}