#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("perle.in");
ofstream fout("perle.out");
int v[10005], n, t, i, j, ok, nrc=0;
char sir[10005], ch[5];
void funct(int in, int i)
{
    if(sir[in]=='B')
    {
        if(v[i]==2)
        {
                sir[in+1]='B';
                funct(in+1, i+1);
        }
        else
            if(v[i]==1 && v[i+2]==3 && i<=n-4)
            {
                 nrc++;
                 funct(in+4, i+4);
            }
    }
    else
    if(nrc)
    {
        nrc--;
        if(v[i]==2)
        {
            if(i==n) ok=1;
            else funct(in+1, i+1);
        }
        else
             if(v[i]==1 && v[i+1]==2)
             {
                 if(i+2==n) ok=1;
                 else funct(in+1, i+3);
             }
        else
            if(v[i]==3)
            {
                sir[in+1]='B'; nrc++;
                funct(in+1, i+1);
            }
    }
}
int main()
{
    fin >> t;
    for(j=1; j<=t; j++)
    {
        fin >> n;
        for(i=1; i<=n; i++)
            fin >> v[i];
        ok=0;
        if(n==1)   fout << 1 << "\n";
        else
        {
            if(v[1]==2)
            {
                sir[2]='B';
                funct(2, 2);
            }
            else
                if(v[1]==3)
                {
                    sir[2]='B'; sir[3]='C'; nrc=1;
                    funct(2, 2);
                }
            else
            {
                if(v[1]==1 && v[3]==3)
                {
                    sir[5]='C'; nrc=1;
                    funct (5, 5);
                }
                if(v[1]==1 && v[2]==2 && n==3)   ok=1;
            }
            fout << ok << "\n";
        }
    }


    return 0;
}