#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){
            out<<1<<"\n";
            continue;
        }
        else if(m==2){
            in>>x;
            out<<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){
            in>>x;
            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;
        }
        if(s.length()!=m)
            a=0;
        out<<a<<"\n";
    }
    return 0;
}