#include <stdio.h>
#include <string.h>
int n,l;
char s[20000],s2[20000];
int tr(int poz)
{
    if (poz>l)
     return 0;
    if (poz==l)
     if (strcmp(s,s2)==0)
      return 1;
     else
      return 0;
    int ok1=0,ok2=0,ok3=0;
    char p[20000];
    p[0]=NULL;
    if (s2[poz+1]!=NULL)
     strcpy(p,s2+poz+1);
    switch(s2[poz])
    {
        case 'a':if (s[poz]=='1'){s2[poz]='1';s2[poz+1]=NULL;if (p) strcat(s2,p);ok1=tr(poz+1);}
                 else if (s[poz]=='2'){s2[poz]='2';s2[poz+1]=NULL;if (p) strcat(s2,p);ok2=tr(poz+1);}
                 else {s2[poz]='3';s2[poz+1]=NULL;if (p) strcat(s2,p);ok3=tr(poz+1);}
                 break;
        case 'b':if (s[poz]=='2'){s2[poz]='2';s2[poz+1]='b';s2[poz+2]=NULL;if (p) strcat(s2,p);ok1=tr(poz+1);}
                 else if (s[poz]=='1'){s2[poz]='1';s2[poz+1]='a';s2[poz+2]='3';s2[poz+3]='a';s2[poz+4]='c';s2[poz+5]=NULL;if (p) strcat(s2,p);ok2=tr(poz+1);}
                 else return 0;
                 break;
        case 'c':if (s[poz]=='2'){s2[poz]='2';s2[poz+1]=NULL;if (p) strcat(s2,p);ok1=tr(poz+1);}
                 else if (s[poz]=='3'){s2[poz]='3';s2[poz+1]='b';s2[poz+2]='c';s2[poz+3]=NULL;if (p) strcat(s2,p);ok2=tr(poz+1);}
                 else {s2[poz]='1';s2[poz+1]='2';s2[poz+2]='a';s2[poz+3]=NULL;if (p) strcat(s2,p);ok3=tr(poz+1);}
                 break;
        default: if (poz+1<=strlen(s2))ok1=tr(poz+1); else return 0;
                 break;
    }
    return ok1||ok2||ok3;
}
int main()
{
    freopen("perle.in","r",stdin);
    freopen("perle.out","w",stdout);
    scanf("%d\n",&n);
    int i,j;
    for (i=0;i<n;i++)
    {
        scanf("%d ",&l);
        for (j=0;j<l;j++)
         scanf("%c ",&s[j]);
        s[l]=NULL;
        s2[0]='a';
        s2[1]=NULL;
        if (tr(0))
         printf("1\n");
        else
        {
            s2[0]='b';
            s2[1]=NULL;
            if (tr(0))
             printf("1\n");
             else
             {
                 s2[0]='c';
                 s2[1]=NULL;
                 if (tr(0))
                  printf("1\n");
                 else
                  printf("0\n");
            }
        }
    }
    return 0;
}