#include <bits/stdc++.h>
#define INFILE "perle.in"
#define OUTFILE "perle.out"
using namespace std;
ifstream in(INFILE);
ofstream out(OUTFILE);
/*
  A -> 1 | 2 | 3
  B -> 2B | 1A3AC
  C -> 2 | 3BC | 12A
*/
void Transform(stack<char>&s1,char c1,char c2){
    s1.pop();
    if(c1=='A'){
        s1.push(c2);
    }
    else if(c1=='B'){
        if(c2=='2'){
            s1.push('B');
            s1.push('2');
        }
        else if(c2=='1'){

            s1.push('C');
            s1.push('A');
            s1.push('3');
            s1.push('A');
            s1.push('1');
        }
    }
    else if(c1=='C'){
        if(c2=='2'){
            s1.push('2');
        }
        else if(c2=='3'){

            s1.push('C');
            s1.push('B');
            s1.push('3');

        }
        else if(c2=='1'){
            s1.push('A');
            s1.push('2');
            s1.push('1');
        }
    }
}
void ShowStack(stack<char> s){
    while(!s.empty()){
        cout<<s.top();
        s.pop();
    }
    cout<<"\n";
}
bool canTransform(stack<char>& s1,stack<char>& s2){
    //ShowStack(s1);
    //ShowStack(s2);
    //cout<<"~~~\n";
    if(s1.size()>s2.size())
        return false;
    if(s1.empty()&&s2.empty())
        return true;
    if(s1.empty())
        return false;
    if(s2.empty())
        return false;
    if(s1.top()=='B'&&s2.top()=='3')
        return false;
    if(s2.top()!='1'&&s2.top()!='2'&&s2.top()!='3')
        return false;
    char c1=s1.top();
    char c2=s2.top();
    if(c1==c2){
        s1.pop();
        s2.pop();
    }
    else{
        Transform(s1,c1,c2);
    }
    return canTransform(s1,s2);
}

bool OK(stack<char>&s){
    stack<char> A;
    A.push('A');
    stack<char> B;
    B.push('B');
    stack<char> C;
    C.push('C');
    stack<char> s1(s);
    stack<char> s2(s);
    stack<char> s3(s);
    return (canTransform(A,s1)||canTransform(B,s2)||canTransform(C,s3));
    //return false;
}

int main(){
    int N;
    in>>N;
    for(int i=1;i<=N;i++){
        int len;
        in>>len;
        stack<char> s;
        char vec[len+1];
        for(int i=0;i<len;i++)
            in>>vec[i];
        for(int i=len-1;i>=0;i--)
            s.push(vec[i]);
        out<<OK(s)<<"\n";
    }
    return 0;
}