#include<fstream>
std::ifstream F("perle.in");
std::ofstream G("perle.out");
char x[10001],s[10001],*p;
short n,k,r;
bool o;
int main()
{
    for(F>>r;r--;G<<(!o||*p!='\0'||k>0?"0\n":"1\n")) {
        for(F>>n,k=0;k<n;F>>x[k],++k);
        x[n]='\0',k=0,p=x,o=1;
        if(n==1)
            ++p;
        else if(n==3)
            if(*p=='1'&&*(p+1)=='2')
                p+=3;
            else
                o=0;
        else
            s[++k]=(*p=='3'?'C':'B');
        for(;k>0&&*p!='\0'&&o==1;)
            if(s[k--]=='B')
                if(*p=='2')
                    ++p,s[++k]='B';
                else if(*p=='1'&&*(p+1)&&*(p+2)=='3'&&*(p+3))
                    p+=4,s[++k]='C';
                else
                    o=0;
            else if(*p=='2')
                ++p;
            else if(*p=='3')
                s[++k]='C',s[++k]='B',++p;
            else if(*p=='1'&&*(p+1)=='2'&&*(p+2))
                p+=3;
            else
                o=0;
    }
    return 0;
}