#include <bits/stdc++.h>

using namespace std;

ifstream in("perle.in");
ofstream out("perle.out");

const int DIM = 1e5 + 7;

int v[DIM];
int k, ok;

void A();
void B();
void C();

void A()
{
    if(k == n+1) ok = 0;
    k++;
}
void B()
{
    if(k == n+1) ok = 0;
    if(v[k] == 2 && k != n) k++, B();
    else if(v[k] == 1 && v[k+2] == 3) k+=4, C();
}
void C()
{
    if(k == n+1) ok = 0;
    if(v[k] == 2) k++;
    else if(v[k] == 3) k++, B(), C();
    else if(v[k] == 1 && v[k+1] == 2) k+=2, A();
}

void getStart()
{
    if(n == 1) A();
    else if(v[1] == 2 || (v[1] == 1 && n != 3)) B();
    else C();
}



int main()
{
    in >> q;
    while(q--)
    {
        in >> n;

        k = ok = 1;
        for(int i=1; i<=n; i++)
            in >> v[i];

        getStart();
        if(k == n+1 && ok)
            out << 1 << '\n';
        else
        out << 0 << '\n';
    }
    return 0;
}