#include <fstream>

using namespace std;
fstream f,g;
char sir[10001];
int k;

int valid()
{
   if(k==1)
     return 1;
 
   int flag=0;
   string aux="";
   int x=0;
   
   if(sir[0] == '3')
   {
    aux += 'C';
    while(x<k)
    {
              
       switch(aux[x])
       {
           case 'A':
                aux[x] = sir[x];
                break;
           case 'B':
                if(sir[x] == '2')
                  aux = aux.substr(0,x)+"2B"+aux.substr(x+1,10000);
                if(sir[x] == '1')
                  aux = aux.substr(0,x)+"1A3AC"+aux.substr(x+1,10000);
              break;
          case 'C':
                if(sir[x] == '1')           
                     aux = aux.substr(0,x)+"12A"+aux.substr(x+1,10000);
                if(sir[x] == '2')           
                     aux[x]=sir[x];
                if(sir[x] == '3')           
                     aux = aux.substr(0,x)+"3BC"+aux.substr(x+1,10000);
               break;
       } 
       x++;          
    }     
    if(aux.size()>k||aux[aux.size()-1]>=65)
      return 0;
    if(x==k)
      return 1;    
   }
   else
   {
          aux += 'B';
           while(x<k)
    {
              
       switch(aux[x])
       {
           case 'A':
                aux[x] = sir[x];
                break;
           case 'B':
                if(sir[x] == '2')
                  aux = aux.substr(0,x)+"2B"+aux.substr(x+1,10000);
                if(sir[x] == '1')
                  aux = aux.substr(0,x)+"1A3AC"+aux.substr(x+1,10000);
              break;
          case 'C':
                if(sir[x] == '1')           
                     aux = aux.substr(0,x)+"12A"+aux.substr(x+1,10000);
                if(sir[x] == '2')           
                     aux[x]=sir[x];
                if(sir[x] == '3')           
                     aux = aux.substr(0,x)+"3BC"+aux.substr(x+1,10000);
               break;
       } 
       x++;          
     }     
     if(aux.size()>k||aux[aux.size()-1]>=65)
      return 0;
     
      return 1;    
   
    }
   return flag;
}


void readLine()
{
   f >> k;
   for(int i=0;i<k;i++)
      f >> sir[i];     
}

int main()
{
    int n;
    f.open("perle.in",fstream::in);
    g.open("perle.out",fstream::out);    
    f >> n;
    for(int i=0;i<n;i++)
      {
      readLine();
       g << valid() << "\n";
      } 
    g.close();
    return 0;
}