#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)
{
    if(s.size()>x || ok==1)return;
    string s2="";
    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++)
        {
            s2="";
            if(i!=0)
            s2.append(s,0,i);
            s2.append(v[s[i]-'A'+1][j]);
            if(i+1<s.size())
            s2.append(s.begin()+i+1,s.end());
            rec(i+1,s2);
        }
    }

}
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;
        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)rec(i,"A");
        else if(ok==0)rec(i,"B");
        if(ok==0)rec(i,"C");
        fout<<ok<<'\n';
    }
    return 0;
}