#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]="1A3AC", p[2][2]="2B";
    p[3][1]="12A", p[3][2]="2", p[3][3]="3BC";
}

void gen(string s, string d, int z){
    if(s==d){x=true; return;}
    if(z>=d.size())return;
    if('1'<=s[z]&&s[z]<='3'){
        if(d[z]!=s[z])return;
        gen(s, d, z+1);
    }else if(s[z]=='A'){
        s[z]=d[z];
        gen(s, d, z+1);
    }else if(s[z]=='B'){
        if(d[z]=='1'){
            if(z<=d.size()-5){
                if(d[z+2]=='3'){
                    s.erase(z, 1);
                    s.insert(z, "1A3AC");
                    gen(s, d, z+1);
                }
            }
        }else if(d[z]=='2'){
            if(z<=d.size()-2){
                s.erase(z, 1);
                s.insert(z, "2B");
                gen(s, d, z+1);
            }
        }
    }else{
        if(d[z]=='1'){
            if(z<=d.size()-3){
                if(d[z+1]=='2'){
                    s.erase(z, 1);
                    s.insert(z, "12A");
                    gen(s, d, z+1);
                }
            }
        }else if(d[z]=='2'){
            s[z]='2';
            gen(s, d, z+1);
        }else{
            if(z<=d.size()-3){
                if(d[z]=='3'){
                    s.erase(z, 1);
                    s.insert(z, "3BC");
                    gen(s, d, z+1);
                }
            }
        }
    }
}

int main(){
    init();
    int n, m;
    char c;
    in>>n;
    string a, b;
    for(int i=1; i<=n; i++){
        a.clear();
        in>>m;
        for(int j=1; j<=m; j++)in>>c, a+=c;
        if(a.size()==1){out<<1<<"\n";continue;}
        if(a[0]=='1'){
            if(a[1]=='2')b="12A",b[2]=a[2];
            else b="1A3AC", b[1]=a[1], b[3]=a[3];
        }else if(a[0]=='2'){
            b="2B";
        }else{
            b="3BC";
        }
        x=false;
        gen(b, a, 0);
        out<<x<<"\n";
    }
    return 0;
}