#include <iostream>
#include <fstream>
using namespace std;
ifstream in("perle.in");
ofstream out("perle.out");
bool x;
string d;
void gen(string s, int z){
    if(s==d){x=true; return;}
    if(z>=d.size())return;
    if(s[z]=='B'){
        if(d[z]=='1'){
            s.erase(z, 1);
            s.insert(z, "1A3AC");
            s[z+1]=d[min(int(d.size()-1), z+1)];
            s[z+3]=d[min(int(d.size()-1), z+3)];
            gen(s, z+4);
        }else if(d[z]=='2'){
            s.erase(z, 1);
            s.insert(z, "2B");
            gen(s, z+1);
        }
    }else if(s[z]=='C'){
        if(d[z]=='1'){
            if(d[z+1]=='2'){
                s.erase(z, 1);
                s.insert(z, "12A");
                s[z+2]=d[min(int(d.size()-1), z+2)];
                gen(s, z+2);
            }
        }else if(d[z]=='2'){
            s[z]='2';
            gen(s, z+1);
        }else{
            if(d[z]=='3'){
                s.erase(z, 1);
                s.insert(z, "3BC");
                gen(s, z+1);
            }
        }
    }else{
        gen(s, z+1);
    }
}

int main(){
    int n, m, p;
    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;}
        p=0;
        if(a[0]=='1'){
            if(a[1]=='2'){
                b="12A";
                if(a.size()==3)x=true;
                out<<x<<"\n";
                continue;
            }else{
                b="1A3AC", b[1]=a[1], b[3]=a[3], p=4;
            }
        }else if(a[0]=='2'){
            b="2B";
            p=1;
        }else{
            b="3BC";
            p=1;
        }
        x=false;
        d=a;
        gen(b, p);
        out<<x<<"\n";
    }
    return 0;
}