/* 
 * File:   main.cpp
 * Author: virtualdemon
 *
 * Created on January 23, 2010, 10:24 AM
 */
#include <cstring>
#include <fstream>
#include <cstdlib>
#define Nmax 400005

/*
 *
 */
using namespace std;
ofstream out;
void insert( char s[], const char what[], unsigned int where )
{
    char* aux;
    aux=(char*)calloc( strlen(s)+strlen(what), sizeof(char) );
    strncpy( aux, s, where );
    strcat( aux, what );
    strcat( aux, s+where+1 );
    strcpy( s, aux );
    delete[] aux;
}
void solve( char s[], unsigned int length )
{
     if( 1 == length )
    {
        out<<"1\n";
        return;
    }
    if( 2 == length )
    {
        out<<"0\n";
        return;
    }
    if( 3 == length )
    {
        if( '1' == s[0] && '2' == s[2] )
            out<<"1\n";
        else out<<"0\n";
        return;
    }
    if( 4 == length )
    {
        out<<"0\n";
        return;
    }
    if( 5 == length )
    {
        if( '1' == s[0] && '3' == s[4] && '2' == s[10] )
            out<<"1\n";
        else out<<"0\n";
        return;
    }
     char perle[Nmax];
     unsigned int i;
     if( '1' == s[0] )
        strcpy( perle, "1 A 3 A C" );
    else if( '2' == s[0] )
            strcpy( perle, "2 B" );
         else if( '3' == s[0] )
               strcpy( perle, "3 B C" );
     for( i=0; i < strlen(perle); i+=2 )
     {
         if( strlen(perle) > strlen(s) )
         {
             out<<"0\n";
             return;
         }
         if( 'A' == perle[i] )
             continue;
         if( perle[i] >= '0' && perle[i] <= '3' )
         {
             if( s[i] != perle[i] )
             {
                 out<<"0\n";
                 return;
             }
             continue;
         }
         if( 'B' == perle[i] )
         {
             switch( s[i] )
             {
                 case '1' : insert( perle, "1 A 3 A C", i ); break;
                 case '2' : insert( perle, "2 B", i ); break;
                 default  : out<<"0\n";   return;
             }
             continue;
         }
         if( 'C' == perle[i] )
         {
             switch( s[i] )
             {
                 case '1' : insert( perle, "1 2 A", i ); break;
                 case '2' : perle[i]='2'; break;
                 case '3' : insert( perle, "3 B C", i ); break;
             }
         }
     }
     out<<"1\n";
}
int main()
{char s[Nmax];
unsigned int n, m, i;
    ifstream in("perle.in");
    in>>n;
    out.open("perle.out");
    for( i=0; i < n; ++i )
    {
        in>>m;
        in.getline( s, Nmax );
        solve( s, m );
    }
    return 0;
}