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


    return 0;
}