#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("perle.in");
ofstream g("perle.out");
int ok;
char s[10001];
void inceput();
void lita(int i,char c);
void cuv1(int i);
void cuv2(int i);
void cuv1(int i,int x)
{ char *p,o[10001];
int j;
strcmp(o,s);
    s[i]='B';

    strcpy(s+i+1,s+i+x+1);
    if(strlen(s)==1) {ok=1; return;}
    else
    {
        p=strstr(s,"2B");
        while(p)
        {
            cuv1(p-s,2);
            p=strstr(p,"2B");
        }
        p=strstr(s,"1A3AC");
         while(p)
        {
            cuv1(p-s,5);
            p=strstr(p,"1A3AC");
        }
        p=strstr(s,"3BC");
        while(p)
        {
            cuv2(p-s);
            p=strstr(p,"3BC");
        }
        p=strstr(s,"12A");
         while(p)
        {
            cuv2(p-s);
            p=strstr(p,"12A");
        }
       for(j=0;j<strlen(s);j++)
            {if(s[j]=='1'||s[j]=='2'||s[j]=='3')lita(j,'A');
             if(s[j]=='2') lita(j,'C');}
    }
    strcmp(s,o);
}
void cuv2(int i)
{
    char *p,o[10001];
int j;
strcmp(o,s);
    s[i]='C';
    strcpy(s+i+1,s+i+4);

    if(strlen(s)==1) {ok=1; return;}
    else
    {
        p=strstr(s,"2B");
        while(p)
        {
            cuv1(p-s,2);
            p=strstr(p,"2B");
        }
        p=strstr(s,"1A3AC");
         while(p)
        {
            cuv1(p-s,5);
            p=strstr(p,"1A3AC");
        }
        p=strstr(s,"3BC");
        while(p)
        {
            cuv2(p-s);
            p=strstr(p,"3BC");
        }
        p=strstr(s,"12A");
         while(p)
        {
            cuv2(p-s);
            p=strstr(p,"12A");
        }
        for(j=0;j<strlen(s);j++)
            {if(s[j]=='1'||s[j]=='2'||s[j]=='3')lita(j,'A');
             if(s[j]=='2') lita(j,'C');}

    }
    strcmp(s,o);
}
void lita(int i,char c)
{

     char *p;
int j;
char d=s[i];
    s[i]=c;

    p=strstr(s,"2B");
        while(p)
        {
            cuv1(p-s,2);
            p=strstr(p,"2B");
        }
        p=strstr(s,"1A3AC");
         while(p)
        {
            cuv1(p-s,5);
            p=strstr(p,"1A3AC");
        }
        p=strstr(s,"3BC");
        while(p)
        {
            cuv2(p-s);
            p=strstr(p,"3BC");
        }
        p=strstr(s,"12A");
         while(p)
        {
            cuv2(p-s);
            p=strstr(p,"12A");
        }
        for(j=0;j<strlen(s);j++)
            {if(s[j]=='1'||s[j]=='2'||s[j]=='3')lita(j,'A');
             if(s[j]=='2') lita(j,'C');}
             s[i]=d;
}
void inceput()
{
     char *p;
int j;

    if(strlen(s)==1) {ok=1; return;}
    else
    {
        p=strstr(s,"2B");
        while(p)
        {
            cuv1(p-s,2);
            p=strstr(p,"2B");
        }
        p=strstr(s,"1A3AC");
         while(p)
        {
            cuv1(p-s,5);
            p=strstr(p,"1A3AC");
        }
        p=strstr(s,"3BC");
        while(p)
        {
            cuv2(p-s);
            p=strstr(p,"3BC");
        }
        p=strstr(s,"12A");
         while(p)
        {
            cuv2(p-s);
            p=strstr(p,"12A");
        }
        for(j=0;j<strlen(s);j++)
            {if(s[j]=='1'||s[j]=='2'||s[j]=='3')lita(j,'A');
             if(s[j]=='2') lita(j,'C');}
    }
}
int main()
{ int n,x,i,m,j;

    f>>n;
    for(i=1;i<=n;i++)
    {
        f>>m;
        for(j=1;j<=m;j++)
            {f>>x;
            s[j-1]=x+'0';
            }
            s[m]=0;

            inceput();
     if(ok)g<<1<<'\n';
     else g<<0<<'\n';
     ok=0;
    }
    return 0;
}