#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("perle.in");
ofstream fout("perle.out");
int N,t,tt;
string a;
int ok,nr[4],numar,x;
string v[4][4];
void rec(int i,string s,int poz)
{
    char car=s[i];
    s.erase(i,1);
    s.insert(i,v[car-'A'+1][poz]);
    if(s.size()>x || ok==1)return;
    while(isdigit(s[i]) && i<s.size() && a[i]==s[i])i++;
    if(isdigit(s[i]) && i<s.size() && a[i]!=s[i])return ;
    if(i==s.size())
    {
        if(s.size()==x)ok=1;
        return;
    }
    else for(int j=1;j<=nr[s[i]-'A'+1] && ok==0;j++)
    rec(i,s,j);
}
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(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)
        {
             for(int j=1;j<=2 && ok==0;j++)
                rec(i,"B",j);
        }
        if(ok==0)
        {
            for(int j=1;j<=3 && ok==0;j++)
                rec(i,"C",j);
        }
        fout<<ok<<'\n';
    }
    return 0;
}