#include <bits/stdc++.h>

using namespace std;

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

const int maxn = 10005;
vector<string> str[256];

string ss;

bool pos(vector<char> s, int k) {
    if(k == ss.size() && s.size() == 0) return 1;
    else if(k >= ss.size() && s.size() > 0) return 0;
    if(s.size() == 0) return 0;
    bool ok = 0;
    if(s[0] == ss[k]) {
        vector<char> nxt(s.begin() + 1, s.end());

        ok |= pos(nxt, k + 1);
    }
    else for(auto c : str[s[0]]) {
        if(c[0] == ss[k]) {
            vector<char> nxt(c.begin() + 1, c.end());
            nxt.insert(nxt.end(), s.begin() + 1, s.end());
            ok |= pos(nxt, k + 1);
        }
    }
    return ok;
}

int main() {
    str['A'].push_back("1");
    str['A'].push_back("2");
    str['A'].push_back("3");
    str['B'].push_back("2B");
    str['B'].push_back("1A3AC");
    str['C'].push_back("2");
    str['C'].push_back("3BC");
    str['C'].push_back("12A");
    int q;
    string a;
    fin >> q;
    getline(fin, a);
    while(q--) {
        getline(fin, a);
        int i = 0;
        while(a[i] != ' ') ++i;
        ++i;
        ss.clear();
        for(; i < a.size(); i += 2) {
            ss += a[i];
        }
        fout << (pos({'A'}, 0) || pos({'B'}, 0) || pos({'C'}, 0)) << "\n";
    }
    return 0;
}