#include<iostream>
#include<fstream>
#include<cstring>
using namespace std;
fstream fin("perle.in",ios::in),fout("perle.out",ios::out);
char x[100],lx,y[100],ly;
int r;
int perle(char x[],int i,int j)
{
    char aux;
    //cout<<"x: "<<x<<endl<<"y: "<<y<<endl<<"i: "<<i<<endl;
    //cin>>r;
    if(i==lx)
    {
        if(strcmp(x,y)==0)
        {
            //cout<<endl<<"ggggggggggggggggggggggggggggggggggggggg"<<endl;
            fout<<"1\n";
            return 0;
        }
        else
        {
            fout<<"0\n";
        }
    }
    if(x[i]==y[j])
    {
        perle(x,i+1,j+1);
    }
    if(y[j]=='A'&&x[i]<'4'&&x[i]>'0')
    {
        aux=y[j];
        y[j]=x[i];
        perle(x,i+1,j+1);
        y[j]=aux;
    }
    if(y[j]=='C'&&x[i]=='2')
    {
        aux=y[j];
        y[j]=x[i];
        perle(x,i+1,j+1);
        y[j]=aux;
    }
    if(y[j]=='B'&&x[i]=='1')
    {
        memcpy(y+j+5,y+j+1,100-j-1);
        memcpy(y+j,"1A3AC",5);
        //y[j+5]=0;
        perle(x,i,j);
        memcpy(y+j+1,y+j+5,100-j-5);
        y[j]='B';
    }
    if(y[j]=='B'&&x[i]=='2')
    {
        memcpy(y+j+2,y+j+1,100-j-1);
        memcpy(y+i,"2B",2);
        //y[j+2]=0;
        perle(x,i,j);
        memcpy(y+j+1,y+i+2,100-j-2);
        y[j]='B';
    }
    if(y[j]=='C'&&x[i]=='1')
    {
        memcpy(y+j+3,y+j+1,100-j-1);
        memcpy(y+j,"12A",3);
        //y[j+3]=0;
        perle(x,i,j);
        memcpy(y+j+1,y+j+3,100-j-3);
        y[j]='C';
    }
    if(y[j]=='C'&&x[i]=='3')
    {
        memcpy(y+j+3,y+j+1,100-j-1);
        memcpy(y+j,"3BC",3);
        //y[j+3]=0;
        perle(x,i,j);
        memcpy(y+j+1,y+j+3,100-j-3);
        y[j]='C';
    }
}
int main()
{
    int i,j,a,b,n;
    fin>>n;
    for(i=1;i<=n;i++)
    {
        memset(x,0,sizeof(x));
        memset(y,0,sizeof(y));
        fin>>a;
        for(j=0;j<a;j++)
        {
            fin>>x[j];
        }
        lx=strlen(x);
        if(x[0]=='1'&&lx>3)
        {
            strcpy(y,"1A3AC");
        }

        if(x[0]=='1'&&lx==3)
        {
            strcpy(y,"12A");
        }

        if(x[0]=='2'&&lx>1)
        {
            strcpy(y,"2B");
        }

        if(x[0]=='3'&&lx>1)
        {
            strcpy(y,"3BC");
        }

        ly=strlen(y);
        if(lx==1)
        {
            fout<<"1\n";
        }
        else
        {
            perle(x,0,0);
        }
    }
    fout.close();
    fin.close();
    return 0;
}