#include<fstream>

using namespace std;

int  main(void)
{
  fstream f("perle.in",ios::in),g("perle.out",ios::out);
  if(!f || !g) return 0;
  char x[10001],st[10001],*p;
  int i,n,k,ok,nr,j;
  f>>nr;
  for(i=1;i<=nr;i++)
  {
    f>>n;
    for(j=0;j<n;j++)
      f>>x[j];
    x[n]='\0'; k=0; p=x;  ok=1;
    if(n==1)
      p++;
    else
      if(n==3)
	if(*p=='1' && *(p+1)=='2')
	  p+=3;
	else
	  ok=0;
      else
	if(*p=='3')
	  st[++k]='C';
	else
	  st[++k]='B';
    while(k>0 && *p!='\0' && ok==1)
      if(st[k--]=='B')
	if(*p=='2')
	{
	  p++; st[++k]='B';
	}
	else
	  if(*p=='1' && *(p+1) && *(p+2)=='3' && *(p+3))
	  {
	    p+=4; st[++k]='C';
	  }
	  else
	    ok=0;
      else //'C'
	if(*p=='2')
	  p++;
	else
	  if(*p=='3')
	  {
	    st[++k]='C'; st[++k]='B'; p++;
	  }
	  else
	    if(*p=='1' && *(p+1)=='2' && *(p+2))
	      p+=3;
	    else
	      ok=0;
    if(ok==0 || *p!='\0' || k>0)
      g<<"0\n";
    else
      g<<"1\n";
  }
  f.close(); g.close();

  return 0;
}