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

/*
 *
 */
using namespace std;
ofstream out;
const char B[][6]={ "2B", "1A3AC" }, C[][4]={ "3BC", "12A" };
void insert( char s[], const char what[], unsigned where )
{
    char *aux;
    aux=new char[strlen(s)+strlen(what)+1];
    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[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, B[1] );
    else if( '2' == s[0] )
            strcpy( perle, B[0] );
        else if( '3' == s[0] )
               strcpy( perle, C[0] );
    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, B[1], i );
            else if( '2' == s[i] )
                    insert( perle, B[0], 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, C[0], i );
                 else insert( perle, C[1], i );
        }
    }
    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.get( s, Nmax );
        solve( s, m );
    }
    return 0;
   
}