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

/*
 *
 */
using namespace std;
ofstream out;
inline  void insert(char c[],const char wcopy[],int i)
{char aux[Nmax],aux2[Nmax];
   memset(aux,0,sizeof(aux)); memset(aux2,0,sizeof(aux2));
	strncpy(aux,c,i);
   strcpy(aux2,c+i+1);
	memset(c,0,sizeof(c));
	strcpy(c,aux); strcat(c,wcopy); strcat(c,aux2);
}

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[1] )
            out<<"1\n";
        else out<<"0\n";
        return;
    }
    if( 4 == length )
    {
        out<<"0\n";
        return;
    }
    if( 5 == length )
    {
        if( '1' == s[0] && '3' == s[2] && '2' == s[4] )
            out<<"1\n";
        else out<<"0\n";
        return;
    }
    char perle[Nmax];
    unsigned int i;
    if( '1' == s[0] )
        strcpy( perle, "1A3AC" );
    else if( '2' == s[0] )
            strcpy( perle, "2B" );
        else if( '3' == s[0] )
               strcpy( perle, "3BC" );
    for( i=0; i < strlen(perle); ++i )
    {
        if( strlen(perle) > length )
        {
            out<<"0\n";
            return;
        }
        if( 'A' == perle[i] )
            continue;
        if( perle[i] >= '0' && perle[i] <= '9' )
        {
            if( s[i] != perle[i] )
            {
                out<<"0\n";
                return;
            }
            continue;
        }
        if( 'B' == perle[i] )
        {
            if( '1' == s[i] )
                insert( perle, (char*)"1A3AC", i );
            else if( '2' == s[i] )
                    insert( perle, (char*)"2B", i );
                else {
                        out<<"0\n";
                        return;
                     }
            continue;
        }
        if( 'C' == perle[i] )
        {
            if( '2' == s[i] )
                perle[i]='2';
            else if( '3' == s[i] )
                   insert( perle, (char*)"3BC", i );
                 else insert( perle, (char*)"12A", i );
        }
    }
    out<<"1\n";
}
int main()
{char s[Nmax]="21A3AC";
 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 );
        remove( s, s+strlen(s)+1, ' ');
        solve( s, m );
    }
    return 0;   
}