#include <bits/stdc++.h>
using namespace std;
ifstream in("perle.in");
ofstream out("perle.out");
int main(){
    int n,m,i;
    char x;
    bool a;
    string s;
    in>>n;
    while(n--){
        in>>m>>x;
        if(m==1){
            cout<<1<<"\n";
            continue;
        }
        else if(m==2){
            cin>>x;
            cout<<0<<"\n";
            continue;
        }
        if(x=='2')
            s="2B";
        else if(x=='1'){
            if(m==3)
                s="12A";
            else
                s="1A3AC";
        }
        else
            s="3BC";
        i=1;
        a=1;
        while(i<m){
            cin>>x;
            //cout<<i<<" : "<<x<<" ";
            //cout<<s<<" "<<a<<"\n";
            if(a){
                if(s[i]=='A');
                else if(s[i]=='B'){//cout<<"a";
                    if(x=='2'){
                        s.replace(i,1,"");
                        s.insert(i,"2B");
                    }
                    else if(x=='1'){
                        s.replace(i,1,"");
                        s.insert(i,"1A3AC");
                    }
                    else
                        a=0;
                }
                else if(s[i]=='C'){
                    if(x=='2'){
                        s.replace(i,1,"");
                        s.insert(i,"2");
                    }
                    else if(x=='1'){
                        s.replace(i,1,"");
                        s.insert(i,"12A");
                    }
                    else{
                        s.replace(i,1,"");
                        s.insert(i,"3BC");
                    }
                }
                else if(s[i]==' ')
                    a=0;
                else if(x!=s[i])
                    a=0;
            }
            ++i;
        }
        out<<a<<"\n";
    }
    return 0;
}