#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
int v[10001];
char c[12002],aux[12002];
int verif(int i,int ct,int n)
{
    int j,k;
    if(i>n && c[ct]==0)
        return 1;
    if(c[ct]==0)
        return 0;
    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 && v[i+2]==3 && i+4<=n)
                {
                    c[ct]='C';
                    i+=4;
                }
                else
                {
                    if(v[i]==2 && i+1<=n)
                    {
                        c[ct]='B';
                        i+=1;
                    }
                    else
                        return 0;
                }
            }
            else
                return 0;
            break;
        case 'C':
            switch(v[i])
            {
                case 1:
                    if(v[i]==1 && v[i+1]==2)
                        c[ct]='A',i+=2;
                    else
                        return 0;
                break;
                case 2:
                    i++;
                    ct++;
                    break;
                case 3:
                    i++;
                    for(k=ct+1; c[k]!=0; k++)
                        aux[k]=c[k];
                    c[ct]='B';
                    c[ct+1]='C';
                    for(j=ct+1; j<k; j++)
                        c[j+1]=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<=12000; j++)
            c[j]=aux[j]=0;
        c[1]='B';
        if(z==0)
            z+=verif(1,1,n);
        for(j=1; j<=12000; j++)
            c[j]=aux[j]=0;
        c[1]='C';
        if(z==0)
            z+=verif(1,1,n);
        for(j=1; j<=12000; j++)
            c[j]=aux[j]=0;
        if(z) printf("1\n");
        else printf("0\n");
    }

    return 0;
}