#include <bits/stdc++.h>
using namespace std;
ifstream fi("perle.in");
ofstream fo("perle.out");

int q;
int n;
string S;
bool ans;

string aplica(string s, int poz, int tip) {
    string ret = "";
    ret += s.substr(0, poz);

    if (s[poz] == 'A') {
        char aux = '0' + tip;
        ret += aux;
    }
    else if (s[poz] == 'B') {
        if (tip == 1)
            ret += "2B";
        else
            ret += "1A3AC";
    }
    else {
        if (tip == 1)
            ret += "2";
        else if (tip == 2)
            ret += "3BC";
        else
            ret += "12A";
    }

    ret += s.substr(poz + 1, s.size() - poz - 1);

    return ret;
}

void iaVezi(string s) {
    // incepem cu s, incercam sa il aducem la S

    string cif = "";
    int indS = 0;

    for (int i = 0; i < s.size(); i++)
        if ('A' <= s[i] && s[i] <= 'C') {
            char vr = S[indS];
            if (s[i] == 'A') {
                s[i] = vr;
                cif += vr;
                indS++;
            }
            else if (s[i] == 'B') {
                if (vr == '1') {
                    s = aplica(s, i, 2);
                    cif += "1";
                    indS++;
                }
                else if (vr == '2') {
                    s = aplica(s, i, 1);
                    cif += "2";
                    indS++;
                }
                else
                    return;
            }
            else {
                if (vr == '2') {
                    s[i] = vr;
                    cif += vr;
                    indS++;
                }
                else if (vr == '1') {
                    s = aplica(s, i, 3);
                    cif += "1";
                    indS++;
                }
                else {
                    s = aplica(s, i, 2);
                    cif += "3";
                    indS++;
                }
            }
        }
        else {
            if (s[i] != S[indS])
                return;

            cif += s[i], indS++;
        }

    if (s == S)
        ans = true;
}

int main()
{
    fi >> q;
    while (q--) {
        fi >> n;
        S.resize(n);
        for (int i = 0; i < n; i++)
            fi >> S[i];

        ans = false;

        iaVezi("A");
        if (!ans)
            iaVezi("B");
        if (!ans)
            iaVezi("C");

        fo << ans << "\n";
    }

    return 0;
}