#include <iostream>
#include <cstdio>
#include <string>
#include <vector>

using namespace std;

int n,l, k, len;
string line, aux;
vector <string> sol[3];

inline void start(){
    sol[0].push_back(" 1");
    sol[0].push_back(" 2");
    sol[0].push_back(" 3");
    sol[1].push_back(" 2 B");
    sol[1].push_back(" 1 A 3 A C");
    sol[2].push_back(" 2");
    sol[2].push_back(" 3 B C");
    sol[2].push_back(" 1 2 A");
}

bool bt(){
    if(aux.length()==len && k>len)
        return 1;
    if(k>len && aux.length()>len)
        return 0;
    if(aux.length()<k)
        return 0;
    if(line[k]==aux[k]){
        k+=2;
        return bt();
    }
    if('1'<=aux[k] && aux[k]<='3')
        return 0;
    for(string s : sol[aux[k]-'A']){
        if(s[1]==line[k]){
            aux.erase(k-1,2);
            aux.insert(k-1, s);
            k+=2;
            return bt();
        }
    }
    return 0;
}

int solve(){
    aux="";
    len=line.length();
    k=1;
    for(int i=0;i<3;++i){
        for(string s : sol[i]){
            k=1;
            if(s[1]==line[k]){
                aux=s;
                k+=2;
                if(bt())
                    return 1;
            }
        }
    }
    return 0;
}

int main()
{
    freopen("perle.in","r",stdin);
    freopen("perle.out","w",stdout);

    start();
    cin>>n;

    for(int i=0;i<n;++i){
        cin>>l;
        getline(cin,line);
        //cout<<l<<"/"<<line<<"\n";
        cout<<solve()<<"\n";
    }

    return 0;
}