#include <stdio.h>

#define DIM 10005

using namespace std;

FILE *fin = fopen("perle.in", "r");
FILE *fout = fopen("perle.out", "w");

int T,n,x,i,vf;
char sir[DIM],stiva[DIM];
bool ok;

int main()
{
    fscanf(fin, "%d", &T);

    while(T)
    {
        fscanf(fin, "%d", &n);
        for(i=0; i<n; ++i)
        {
            fscanf(fin, "%d", &x);
            sir[i] = x+'0';
        }
        sir[n] = NULL;

        vf = -1;
        for(i=0; i<n; ++i)
        {
            if(vf >= 1 and (stiva[vf] == '2' or stiva[vf] == 'A' or stiva[vf]=='C') and (stiva[vf-1] == '1' or stiva[vf-1] == 'A'))
                stiva[--vf] = 'C';
            else
                if(sir[i]=='2' and vf>=3 and stiva[vf]!='B' and stiva[vf-1]=='3' and stiva[vf-2]!='B'
                   and stiva[vf-3]=='1' or stiva[vf-3]=='A')
                {
                    vf -= 3;
                    stiva[vf] = 'B';
                }
                else
                    stiva[++vf] = sir[i];

            ok = 1;
            while(ok)
            {
                ok = 0;
                if(vf>=1 and stiva[vf]=='B' and (stiva[vf-1]=='2' or stiva[vf-1]=='A' or stiva[vf-1]=='C'))
                {
                    stiva[--vf] = 'B';
                    ok = 1;
                }
                else
                    if(vf>=2 and (stiva[vf]=='C' or stiva[vf]=='2') and stiva[vf-1]=='B' and (stiva[vf-2]=='3' or stiva[vf-2]=='A'))
                    {
                        vf -= 2;
                        stiva[vf] = 'C';
                        ok = 1;
                    }
                    else
                        if(vf>=2 and stiva[vf]!='B' and (stiva[vf-1]=='A' or stiva[vf-1]=='2' or stiva[vf-1]=='C') and
                           (stiva[vf-2]=='A' or stiva[vf-2]=='1'))
                        {
                            vf -= 2;
                            stiva[vf] = 'C';
                            ok = 1;
                        }
                        else
                            if(vf>=4 and (stiva[vf]=='C' or stiva[vf]=='2') and stiva[vf-1]!='B' and (stiva[vf-2]=='A' or
                               stiva[vf-2]=='3') and stiva[vf-3]!='B' and (stiva[vf-4]=='1' or stiva[vf-4]=='A'))
                            {
                                vf -= 4;
                                stiva[vf] = 'B';
                                ok = 1;
                            }
            }//while ok
        }//for i

        ok = 1;
            while(ok)
            {
                ok = 0;
                if(vf>=1 and stiva[vf]=='B' and (stiva[vf-1]=='2' or stiva[vf-1]=='A' or stiva[vf-1]=='C'))
                {
                    stiva[--vf] = 'B';
                    ok = 1;
                }
                else
                    if(vf>=2 and (stiva[vf]=='C' or stiva[vf]=='2') and stiva[vf-1]=='B' and (stiva[vf-2]=='3' or stiva[vf-2]=='A'))
                    {
                        vf -= 2;
                        stiva[vf] = 'C';
                        ok = 1;
                    }
                    else
                        if(vf>=2 and stiva[vf]!='B' and (stiva[vf-1]=='A' or stiva[vf-1]=='2' or stiva[vf-1]=='C') and
                           (stiva[vf-2]=='A' or stiva[vf-2]=='1'))
                        {
                            vf -= 2;
                            stiva[vf] = 'C';
                            ok = 1;
                        }
                        else
                            if(vf>=4 and (stiva[vf]=='C' or stiva[vf]=='2') and stiva[vf-1]!='B' and (stiva[vf-2]=='A' or
                               stiva[vf-2]=='3') and stiva[vf-3]!='B' and (stiva[vf-4]=='1' or stiva[vf-4]=='A'))
                            {
                                vf -= 4;
                                stiva[vf] = 'B';
                                ok = 1;
                            }
            }//while ok

        if(vf == 0)
            fprintf(fout, "1\n");
        else
            fprintf(fout, "0\n");

        --T;
    }

    return 0;
}