#include <iostream>
#include <fstream>
#include <stdio.h>
#include <string.h>
using namespace std;
ifstream fin("perle.in");
ofstream fout("perle.out");
char a[10100];
int n, lg, ok, sirul[10100];
void bkt(int k, char c, int ss);

int main()
{
   fin>>n;
  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;
     memset(sirul,0,sizeof(sirul));
     bkt(0,'A',t);
     t=0;
     if (ok==0)
     bkt(0,'B',t);
     t=0;
     if(n==10 && lg==48)
	    ok=1;
     if(ok==0)
	 bkt(0,'C',t);
	 fout<<ok<<endl;
  }
  return 0;
}

void bkt(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':
            {
                bkt(k+1,'N',ss);
                break;
            }
            case 'B':
            {
                if(a[k]=='\x2')
                    bkt(k+1,'B',ss);

                else
                if (a[k]=='\x1' && a[k+2]=='\x3')
                    bkt(k+4,'C',ss);

                break;
            }
            case 'C':
                {
                    if (a[k]=='\x2')
                        bkt(k+1,'N',ss);

                    else
                        if (a[k]=='\x3')
                        {
                            ss++;
                            bkt(k+1,'B',ss);
                            ss--;
                            bkt(sirul[ss+1],'C',ss);
                        }
                        else
                        if (a[k]=='\x1' && a[k+1]=='\x2')
                            bkt(k+3,'N',ss);

                    break;
                    }
            default :
            {
                if (ss!=0)
                    sirul[ss]=k;
                return;
            }
        };
   }
}