#include <iostream>
#include <fstream>
#include <cctype>
using namespace std;
ifstream fin("perle.in");
ofstream fout("perle.out");
int N,t,tt,ch;
string a;
int ok,nr[4],numar,x;
string v[4][4];
void rec(char car,int k)
{
    ch=0;
    if(k>=a.size() || ok==1)return;
    int kk=k,q,j;
    for(j=1;j<=nr[car-'A'+1] && ok==0;j++)
    {
        int imp=1;
        for(q=0,k=kk;q<v[car-'A'+1][j].size();q++,k++)
            if(isalpha(v[car-'A'+1][j][q]))
            {
                rec(v[car-'A'+1][j][q],k);
                if(ch!=0)k+=ch-1;
                else
                {
                    ch=0;
                    imp=-1;
                    break;
                }
            }
            else if(v[car-'A'+1][j][q]!=a[k])
            {
                imp=-1;
                ch=0;
                break;
            }
        if(k>a.size())
        {
            ch=0;
            imp=-1;
        }
        if(imp==1)
        {
            ch=k-kk;
            if(kk==0)if(ch==a.size())ok=1;
            break;
        }
    }

}
int main()
{
    fin>>N;
    v[1][1]="1";v[1][2]="2";v[1][3]="3";
    v[2][1]="2B";v[2][2]="1A3AC";
    v[3][1]="2";v[3][2]="3BC";v[3][3]="12A";
    nr[1]=3;nr[2]=2;nr[3]=3;
    string s;
    getline(fin,s);
    for(t=1;t<=N;t++)
    {
        ok=0;
        numar=0;
        x=0;
        a="";
        getline(fin,s);
        for(unsigned int j=0;j<s.size();j++)
        {
            if(isdigit(s[j]))
            {
                if(numar==0)x=x*10+(s[j]-'0');
                else a.push_back(s[j]);
            }
            else numar=1;
        }
        int i=0;
        if(x==1)ok=1;
        if(ok==0)rec('B',0);
        if(ok==0)rec('C',0);
        fout<<ok<<'\n';
    }
    return 0;
}