#include <bits/stdc++.h>
using namespace std;
ifstream fin ("perle.in");
ofstream fout("perle.out");
int n,p,v[10002];
deque<char>sol;
bool ok;

void a ()
{
    if (v[p]==1||v[p]==2||v[p]==3)
            ++p;
}

void b ()
{
    if (v[p]==2&&p<=n)
    p++;
    else
    if (v[p]==1&&v[p+2]==3&&p+4<=n)
    p+=4,sol.front()='C';
    else ok=0;
}

void c ()
{
    if (v[p]==2&&p<=n)
        ++p,sol.pop_front();
    else
        if (v[p]==3&&p+2<=n)
    {
        p++;
        sol.push_front('B');
    }
    else    if (v[p]==1&&v[p+1]==2&&p+2<=n)
        p+=3,sol.pop_front();
    else    ok=0;
}

void rezolva ()
{
    while (sol.empty()==0&&ok)
    {
    if (sol.front()=='A')
        a();
    else    if (sol.front()=='B')
        b();
    else     if (sol.front()=='C')
        c();
    }
   if (p<n)
    ok=0;
}

int main()
{
    int t,i;
    fin>>t;
    while (t--)
    {
        fin>>n;
        p=1;
        for (i=1;i<=n;i++)
            fin>>v[i];
        if (n==1)
            fout<<1;
        else{
            ok=true;
            if (n==3||v[1]==3)
                sol.push_back('C');
             else   if (v[1]==1||v[1]==2)
                        sol.push_back('B');
            rezolva();
            fout<<ok;
        }
        fout<<'\n';
    }
    return 0;
}