#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
int v[10001];
char aux[10002],c[10002];
int verif(int i,int ct,int n)
{
    int j,k;
    if(i>n && c[ct]==0)
        return 1;
    if(c[ct]==0 && i<=n)
        return 0;
    while(isdigit(c[ct]) && v[i]==c[ct]-'0')
        i++,ct++;
    if(isdigit(c[ct]))
        return 0;
    switch(c[ct])
    {
        case 'A': ct++; i++; break;
        case 'B':
            if(v[i]!=3)
            {
                if(v[i]==1)
                {
                    for(k=ct+1; c[k]!=0; k++)
                        aux[k]=c[k];
                    c[ct]='1';
                    c[ct+1]='A';
                    c[ct+2]='3';
                    c[ct+3]='A';
                    c[ct+4]='C';
                    for(j=ct+1; j<k; j++)
                        c[j+4]=aux[j];
                }
                else
                {
                    for(k=ct+1; c[k]!=0; k++)
                        aux[k]=c[k];
                    c[ct]='2';
                    c[ct+1]='B';
                    for(j=ct+1; j<k; j++)
                        c[j+1]=aux[j];
                }
            }
            else
                return 0;
            break;
        case 'C':
            switch(v[i])
            {
                case 1:
                    for(k=ct+1; c[k]!=0; k++)
                        aux[k]=c[k];
                    c[ct]='1';
                    c[ct+1]='2';
                    c[ct+2]='A';
                    for(j=ct+1; j<k; j++)
                        c[j+2]=aux[j];
                    break;
                case 2:
                    i++;
                    ct++;
                    break;
                case 3:
                    for(k=ct+1; c[k]!=0; k++)
                        aux[k]=c[k];
                    c[ct]='3';
                    c[ct+1]='B';
                    c[ct+2]='C';
                    for(j=ct+1; j<k; j++)
                        c[j+2]=aux[j];
                    break;
            }
            break;
    }
    return verif(i,ct,n);
}
int main()
{
    int t,z,i,n,j;
    freopen("perle.in","r",stdin);
    freopen("perle.out","w",stdout);
    scanf("%d",&t);
    z=0;
    for(i=1; i<=t; i++)
    {
        scanf("%d",&n);
        for(j=1; j<=n; j++)
            scanf("%d",&v[j]);
        z=0;
        c[1]='A';
        z+=verif(1,1,n);
        for(j=1; j<=10000; j++)
            c[j]=aux[j]=0;
        c[1]='B';
        z+=verif(1,1,n);
        for(j=1; j<=10000; j++)
            c[j]=aux[j]=0;
        c[1]='C';
        z+=verif(1,1,n);
        for(j=1; j<=10000; j++)
            c[j]=aux[j]=0;
        if(z) printf("1\n");
        else printf("0\n");
    }

    return 0;
}