#include <stdio.h>
#include <string.h>
#define ml 10007

using namespace std;

FILE *f=fopen("perle.in","r");
FILE *g=fopen("perle.out","w");

int i,N,L,n,p,sl; bool ok;
char s[ml],st[ml];

int main()
{
    fscanf(f,"%d",&N);
    for(i=1;i<=N;i++)
    {
        fscanf(f,"%d",&L);
        for(int l=0;l<L;l++)
        {
            fscanf(f,"%d",&n);
            s[l]='0'+n;
        }
        ok=0;
        if(L==1) ok=1;
        else if(L==3) ok=(s[0]=='1'&&s[1]=='2');
        else if(L==5) ok=(s[0]=='1'&&s[2]=='3'&&s[4]=='2');
        else if(L>6)
        {
            if(s[0]=='1') {strcpy(st,"1A3AC"); p=4;}
            else if(s[0]=='2') {strcpy(st,"2B"); p=1;}
            else {strcpy(st,"3BC"); p=1;}
            while(p<L)
            {
                sl=strlen(s)-p;;
                if(st[p]=='B')
                 if(s[p]=='2')
                 {
                     memmove(st+p+2,st+p+1,sl);
                     memcpy(st+p,"2B",2);
                 }
                 else
                 {
                     memmove(st+p+5,st+p+1,sl);
                     memcpy(st+p,"1A3AC",5);
                 }
                else if(st[p]=='C')
                 if(s[p]=='2')
                  st[p]='2';
                 else if(s[p]=='3')
                 {
                     memmove(st+p+3,st+p+1,sl);
                     memcpy(st+p,"3BC",3);
                 }
                 else
                 {
                     memmove(st+p+3,st+p+1,sl);
                     memcpy(st+p,"12A",3);
                 }
                 if(st[p]!='A'&&st[p]!=s[p]) break;
                 p++;
             }
            ok=(p==L&&L==strlen(st));
        }
        fprintf(g,"%d\n",ok);
    }
    return 0;
}