#include<iostream>
#include<fstream>
#include<cstring>
#define dm 100010
using namespace std;
fstream fin("perle.in",ios::in),fout("perle.out",ios::out);
int n,m;
char x[dm],y[dm],aux;
int f(int ly)
{
    int lx=1,i,j;
    while(lx<=m&&ly>0)
    {
        if(y[ly]==x[lx]||y[ly]=='a')//aaaaaaaaaaaa
        {
            lx++;
            ly--;
            continue ;
        }
        if(y[ly]<'a')
        {
            return 0;
        }
        if(y[ly]=='b')//bbbbbbbbbbb
        {
            if(x[lx]=='2')
            {
                lx++;
            }
            else
            {
                if(x[lx]=='1')
                {
                    lx++;
                    y[ly++]='c';
                    y[ly++]='a';
                    y[ly++]='3';
                    y[ly]='a';
                }
                else
                {
                    return 0;
                }
            }
            continue ;
        }
        if(y[ly]=='c')//cccccccccccccc
        {
            if(x[lx]=='2')
            {
                lx++;
                ly--;
            }
            else
            {
                if(x[lx]=='3')
                {
                    lx++;
                    y[ly++]='c';
                    y[ly]='b';
                }
                else
                {
                   if(x[lx]=='1')
                    {
                        lx++;
                        y[ly++]='a';
                        y[ly]='2';
                    }
                }
            }
            continue ;
        }
    }
    if(lx==m+1&&ly==0)return 1;
    return 0;
}
int main()
{
    int j,i,ly,ok;
    char k;
    fin>>n;
    for(i=1;i<=n;i++)
    {
        fin>>m;
        for(j=1;j<=m;j++)fin>>x[j];
        ok=0;
        for(k='a';k<'d';k++)
        {
            ly=1;
            y[ly]=k;
            if(f(ly))ok=1;
        }
        fout<<ok<<"\n";
    }
    return 0;
}