#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

ifstream f("perle.in");
ofstream g("perle.out");

int n,l=0;
char sir[10002], rezultat[10002];
bool rez=false;

void transf(char val, int k, int poz)
{
    if(val=='A')
    {
        rezultat[poz]=k+1+'0';
        return;
    }
    if(val=='B')
    {
        if(k==0)
        {
            strcpy(rezultat+poz+2,rezultat+poz+1);
            strcpy(rezultat+poz,"2B");
            return;
        }
        strcpy(rezultat+poz+5,rezultat+poz+1);
        strcpy(rezultat+poz,"1A3AC");
        return;
    }
    if(val=='C')
    {
        if(k==0)
        {
            rezultat[poz]='2';
            return;
        }
        if(k==1)
        {
            strcpy(rezultat+poz+3,rezultat+poz+1);
            strcpy(rezultat+poz,"3BC");
            return;
        }

        strcpy(rezultat+poz+3,rezultat+poz+1);
        strcpy(rezultat+poz,"12A");
        return;
    }
    return;
}
void rev_transf(char val, int k, int poz)
{
    rezultat[poz]=val;
    if(val=='B')
    {
        if(k==0)
        {
            strcpy(rezultat+poz+1, rezultat+poz+2);
            return;
        }
        strcpy(rezultat+poz+1, rezultat+poz+5);
        return;
    }

    if(val=='C')
    {
        if(k==0)
            return;
        strcpy(rezultat+poz+1, rezultat+poz+3);
        return;
    }
}
void bt()
{
    int l_rez=strlen(rezultat);
    if(l_rez>l)
        return;
    if(rez==false && strcmp(rezultat,sir)==0)
    {
        rez=true;
        return;
    }
    for(int i=0; i<l_rez; i++)
    {
        if(rezultat[i]>='A')
        {
            for(int k=0; k<rezultat[i]%2+2; k++)
            {
                char aux=rezultat[i];
                transf(rezultat[i],k,i);
                bt();
                if(rez==true)
                    return;
                rev_transf(aux,k,i);
            }
        }
    }
}

int main()
{
    f>>n;
    for(int i=0; i<n; i++)
    {
        rez=false;
        l=0;
        f>>l;
        memset(sir,0,sizeof(sir));
        for(int j=0; j<l; j++)
            f>>sir[j];
        //cout<<sir<<endl;
        if(l==1)
        {
            g<<1<<endl;
            continue;
        }
        rezultat[0]='B';
        bt();
        if(rez==false)
        {
            rezultat[0]='C';
            bt();
        }
        if(rez==true)
            g<<'1'<<endl;
        else
            g<<'0'<<endl;
    }
    return 0;
}