#include <iostream>
#include <fstream>
#include <string>
#define MAX_N 10009
using namespace std;
char sir[MAX_N];
int n; bool ok;
void foo(string s);
bool valid(const string s);
int main()
{
    int t;
    ifstream fin("perle.in");
    ofstream fout("perle.out");
    fin>>t;
    for(;t;--t)
    {
        fin>>n;
        for(int i=1;i<=n;++i)
            fin>>sir[i];
        if(n==1)
            fout<<1<<"\n";
        else
        {
            ok=false;
            foo("b");
            if(!ok)
                foo("c");
            fout<<ok<<"\n";
        }

    }
    fin.close();
    fout.close();
    return 0;
}

bool valid(const string s)
{
    if(s[s.size()-1]<='c'&&s[s.size()-1]>='a')
        return false;
    for(int i=1;i<=n;++i)
        if(s[i-1]!=sir[i])
            return false;

    return true;
}

void foo(string s)
{
    if(n==s.size()&&valid(s))
    {
        ok=true;
        return ;
    }
    if(s.size()>n||ok)
        return ;
    for(int i=0;i<s.size();++i)
    {
        if(s[i]=='a')
        {
            string aux=s;
            aux[i]='1';
            foo(aux);
            aux[i]='2';
            foo(aux);
            aux[i]='3';
            foo(aux);
        }
        else if(s[i]=='b')
        {
            string aux=s;
            if(i+1==s.size())
                foo(aux.replace(i,i+1,"2b"));
            else
                foo(aux.replace(i,i,"2b"));
            aux=s;
            if(i+1==s.size())
                foo(aux.replace(i,i+1,"1a3ac"));
            else
                foo(aux.replace(i,i,"1a3ac"));

        }
        else if(s[i]=='c')
        {
            string aux=s;
            aux[i]='2';
            foo(aux);
            aux[i]=s[i];
            if(i+1==s.size())
                foo(aux.replace(i,i+1,"3bc"));
            else
                foo(aux.replace(i,i,"3bc"));
            aux=s;
            if(i+1==s.size())
                foo(aux.replace(i,i+1,"12a"));
            else
                foo(aux.replace(i,i,"12a"));
        }
    }
}