#include <fstream>

using namespace std;

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

string a;
bool ok;

void perla(string s)
{
    if (s.size() > a.size())
        return;

    if (s == a)
    {
        ok = true;
        return;
    }

    string crt = "";

    for (int i = 0; i < s.size(); ++i)
    {
        if (s[i] == 'A')
        {
            s[i] = '1';
            perla(s);
            s[i] = '2';
            perla(s);
            s[i] = '3';
            perla(s);
        }
        else if (s[i] == 'B')
        {
            if (s[s.size() - 1] == 'C') perla(crt + "2BC");
            else perla(crt + "2B");
            perla(crt + "1A3AC");
        }
        else if (s[i] == 'C')
        {
            perla(crt + "2");
            perla(crt + "3BC");
            perla(crt + "12A");
        }
        else crt = crt + s[i];
    }
}

int main()
{
    int n, m;
    char x;
    fin >> n;
    while(n--)
    {
        ok = 0;
        fin >> m;
        a = "";
        while(m--)
        {
            fin >> x;
            a = a + x;
        }
        perla("A");
        if (!ok)
        {
            perla("B");
            if (!ok)
            {
                perla("C");
            }
        }
        fout << ok << "\n";
    }
    return 0;
}