#include <iostream>
#include <fstream>
using namespace std;
ifstream in("perle.in");
ofstream out("perle.out");
string p[4][4];
int v[]={0, 3, 2, 3};
bool x;
void init(){
    p[1][1]="1", p[1][2]="2", p[1][3]="3";
    p[2][1]="2B", p[2][2]="1A3AC";
    p[3][1]="2", p[3][2]="3BC", p[3][3]="12A";
}

void gen(string s, string d){
    if(x||s.size()>d.size())return;
    if(s==d){
        x=true;
        return;
    }
    string s2=s;
    int l;
    for(int i=0; i<s2.size()&&!x; i++){
        if('A'<=s2[i]&&s2[i]<='C'){
            l=s2[i]-'A'+1;
            for(int j=1; j<=v[l]&&!x; j++){
                if(p[l][j][0]==d[i]){
                    s2.erase(i, 1);
                    s2.insert(i, p[l][j]);
                    gen(s2, d);
                    s2=s;
                    break;
                }
            }
        }
    }
}

int main(){
    init();
    int n, m;
    char c;
    in>>n;
    string a;
    for(int i=1; i<=n; i++){
        a.clear();
        x=false;
        in>>m;
        for(int j=1; j<=m; j++)in>>c, a+=c;
        gen("A", a);
        if(!x)gen("B", a);
        if(!x)gen("C", a);
        out<<x<<"\n";
    }
    return 0;
}