#include <fstream.h>
#include <string.h>
#define MAX 10100

ifstream fin ("perle.in");
ofstream fout ("perle.out");
char a[MAX],sir[MAX];
int n,lg,ok;

void back(int k,char c,int &ss)
{
   if (k==lg && c=='N')
   {
      ok=1;
      return ;
   }
   else
     if (k>lg)
	return;
   if (ok==0)
   {
   switch (c)
   {
      case 'A':
      {
	 back(k+1,'N',ss);
	 break;
      }
      case 'B':
      {
	if (a[k]=='\x2')
	{
   //	   sir[k]='2';
	   back(k+1,'B',ss);
 //	   sir[k]=0;
	}
	else
	  if (a[k]=='\x1' && a[k+2]=='\x3')
	  {
  //	     sir[k]='1';
  //	     sir[k+1]=a[k+1];
  //	     sir[k+2]=a[k+2];
  //	     sir[k+3]==sir[k+3];
	     back(k+4,'C',ss);
	  }
	  break;
      }
      case 'C':
      {
	 if (a[k]=='\x2')
	 {
 //	   sir[k]='2';
	   back(k+1,'N',ss);
	 }
	 else
	   if (a[k]=='\x3')
	   {
	      int k2=k;
	      ss++;
	      back(k2+1,'B',ss);
	      int aux=ss;
	      aux=0;
	      back(ss,'C',aux);
	   }
	   else
	     if (a[k]=='\x1' && a[k+1]=='\x2')
	     {
		back(k+3,'N',ss);
	     }
	   break;
      }
      default :
      {
	 if (ss!=0)
	    ss=k;
	 return;
      }
   };
   }
}

void citire()
{
  fin>>n;
  fin.getline (a,100);
  for (int i=0;i<n;i++)
  {
     fin>>lg;
     char ca;
     a[0]=0;
     for (int j=0;j<lg;j++)
     {
	fin>>ca;
	a[j]=ca-'0';
     }
     ok=0;
     int t=0;
     back(0,'A',t);
     t=0;
     if (ok==0)
	back(0,'B',t);
	t=0;
     if (ok==0)
	back(0,'C',t);
     fout<<ok<<"\n";
  }
}

int main ()
{
  citire();
  return 0;
}