#include <iostream>
#include <fstream>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;

ifstream in("perle.in");
ofstream out("perle.out");

const int MAXN = 11, MAXL = 10001;

int N, ok;

void back2(char *s, char *p)
{
    if( p[ 0 ] == ' ' )
        p++;

    if( strlen( s ) == 0 && strlen( p ) == 0 )
    {
        ok = 1;
        return;
    }

    if( 2*strlen( s ) - 1 <= strlen( p ) )
    {
        if( s[ 0 ] == 'A' )
            back2( s + 1, p + 1 );
        else if( s[ 0 ] == 'B' )
        {
            if( p[ 0 ] == '2' )
                back2( s, p + 1 );

            if( strlen( p ) >= 5 && ( p[ 0 ] == '1' && p[ 4 ] == '3' ) )
                back2( "C", p + 7 );
        }
        else if( s[ 0 ] == 'C' )
        {
            if( p[ 0 ] == '2' )
                back2( s + 1, p + 1 );

            if( p[ 0 ] == '3' )
                back2( "BC", p + 1 );

            if( p[ 0 ] == '1' && p[ 2 ] == '2' && strlen( p ) >= 3 )
                back2( s + 1, p + 5 );
        }
    }
}

void solve()
{
    char *p;

    in>>N;
    in.getline(p,1);

    for(int i = 1; i <= N; i++)
    {
        in.getline(p,MAXL+1);
        strcpy(p,p+2);

        ok = 0;

        back2( "A", p );

        if( ok == 0 )
        {
            back2( "B", p );

            if( ok == 0 )
                back2( "C", p );
        }

        out<<ok<<endl;


    }
}

int main()
{
    solve();

    return 0;
}