#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

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

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

void reversetransf(char val, int k, int poz)
{
    rez[poz]=val;
    if(val=='B')
    {
        if(k==0)
        {
            strcpy(rez+poz+1, rez+poz+2);
            return;
        }
        strcpy(rez+poz+1, rez+poz+5);
        return;
    }
    else if(val=='C')
    {
        if(k==0)
            return;
        strcpy(rez+poz+1, rez+poz+3);
    }
    return;
}

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

void backtracking()
{
    int l_rez=strlen(rez);
    if(l_rez>l)
        return;
    if(strcmp(rez, sir)==0)
    {
        found = true;
        return;
    }
    for(int i=0; i<l_rez; i++)
    {
        if(rez[i]>='A')
        {
            for(int k=0; k<2+(rez[i])%2; k++){
                char cp=rez[i];
                transf(cp, k, i);
                backtracking();
                if(found)
                    return;
                reversetransf(cp, k, i);
            }
        }
        if(rez[i]!=sir[i])
            return;
    }
    return;
}

int main()
{
    f>>n;
    for(int i=0; i<n; i++)
    {
        f>>l;
        found = false;
        memset(sir, 0, sizeof(sir));
        for(int j=0; j<l; j++)
            f>>sir[j];
        if(l==1)
        {
            g<<1<<endl;
            continue;
        }
        rez[0]='B';
        backtracking();
        if(found)
        {
            g<<1<<endl;
            continue;
        }
        rez[0]='C';
        backtracking();
        if(found)
            g<<1<<endl;
        if(!found)
            g<<0<<endl;
    }
    return 0;
}