#include <stdio.h>
#include <string.h>
#include <ctype.h>

using namespace std;
int n,i,j,l,x;
char s1[100100],s[10003],ok;
FILE *f,*g;
void baga (int poz,char s1[],char s3[])
{
    char s2[10004];
    strcpy (s2,s1+poz+1);
    s1[poz]=NULL;
    strcat (s1,s3);
    strcat (s1,s2);
}
int rez (char s[],char s1[])
{  int ok=1;
   for (int k=0;k<l&& ok ;k++)
   {
     if (isdigit (s1[k]) && s[k]!=s1[k]) ok=0;
     if (s1[k]=='B')
     {
         if (s[k]=='1') baga (k,s1,"1A3AC");
           else baga (k,s1,"2B");
     }
     if (s1[k]=='C')
     {
         if (s[k]=='1') baga (k,s1,"12A");
           else if (s[k]=='3') baga (k,s1,"3BC");

     }
   }
   if (strlen (s) !=strlen (s1) || ok==0 ) return 0;
   return 1;
}
int main()
{f=fopen ("perle.in","r");
 g=fopen ("perle.out","w");
 fscanf (f,"%d",&n);
 for (i=1;i<=n;i++)
 {
     fscanf (f,"%d",&l);
     for (j=0;j<l;j++)
          {
              fscanf (f,"%d",&x);
              s[j]=x+'0';

          }

     s[l]=NULL;
     if (l==1) fprintf (g,"1\n");
     else
     {
         if (s[0]=='2') strcpy (s1,"2B");
          else if (s[0]=='3') strcpy (s1,"3BC");
             else strcpy (s1,"1A3AC");
        if (rez (s,s1)) fprintf (g,"1\n");
          else if (s[0]=='1' && rez (s,"12A"))  fprintf (g,"1\n");
           else fprintf (g,"0\n");

     }

 }
    return 0;
}