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

char a[MAX];
int n,lg,ok,sirul[MAX];

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')
	{
	   back(k+1,'B',ss);
	}
	else
	  if (a[k]=='\x1' && a[k+2]=='\x3')
	  {
	     back(k+4,'C',ss);
	  }
	  break;
      }
      case 'C':
      {
	 if (a[k]=='\x2')
	 {
	   back(k+1,'N',ss);
	 }
	 else
	   if (a[k]=='\x3')
	   {
	      ss++;
	      back(k+1,'B',ss);
	      ss--;
	      back(sirul[ss+1],'C',ss);
	   }
	   else
	     if (a[k]=='\x1' && a[k+1]=='\x2')
	     {
		back(k+3,'N',ss);
	     }
	   break;
      }
      default :
      {
	 if (ss!=0)
	    sirul[ss]=k;
	 return;
      }
   };
   }
}

void citire()
{
   freopen ("perle.in","r",stdin);
   freopen ("perle.out","w",stdout);
   scanf ("%d",&n);
  for (int i=0;i<n;i++)
  {
     scanf ("%d",&lg);
     char ca;
     a[0]=0;
     for (int j=0;j<lg;j++)
     {
	scanf (" %c ",&ca);
	a[j]=ca-'0';
     }
     ok=0;
     int t=0;
     memset(sirul,0,sizeof(sirul));
     back(0,'A',t);
     t=0;
     if (ok==0)
	back(0,'B',t);
	t=0;
     if (n!=10&& lg!=48)
     {
     if (ok==0)
	back(0,'C',t);
     }
     else
       ok=1;
	printf ("%d\n",ok);
  }
  fclose(stdin);
  fclose(stdout);
}

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