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

int q;
int n;
string S;
bool ans;
stack <char> stiva;

void bagaStiva(string s) {
    for (int i = s.size() - 1; i >= 0; i--)
        stiva.push(s[i]);
}

void iaVezi(char incipit) {
    // incepem cu incipit, incercam sa il aducem la S

    string cif = "";
    int indS = 0;

    while (!stiva.empty())
        stiva.pop();
    stiva.push(incipit);

    while (!stiva.empty()) {
        char amu = stiva.top();
        stiva.pop();

        if ('A' <= amu && amu <= 'C') {
            char vr = S[indS];
            if (amu == 'A') {
                cif += vr;
                indS++;
            }
            else if (amu == 'B') {
                if (vr == '1') {
                    bagaStiva("A3AC");
                    cif += "1";
                    indS++;
                }
                else if (vr == '2') {
                    bagaStiva("B");
                    cif += "2";
                    indS++;
                }
                else
                    return;
            }
            else {
                if (vr == '2') {
                    cif += vr;
                    indS++;
                }
                else if (vr == '1') {
                    bagaStiva("2A");
                    cif += "1";
                    indS++;
                }
                else {
                    bagaStiva("BC");
                    cif += "3";
                    indS++;
                }
            }
        }
        else {
            if (amu != S[indS])
                return;

            cif += amu, indS++;
        }
    }

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

int main()
{
    fi >> q;
    while (q--) {
        fi >> n;
        S.clear(); 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;
}