#include <fstream>
#include <vector>

using namespace std;

const char iname[] = "perle.in";
const char oname[] = "perle.out";

int T, N, step;
vector < int > V;

bool B();
bool C();

bool A()
{
    if(N == 1)  return 1;

    if(V[step] == 2 || (V[step] == 1 && V[step + 2] == 3 && N >= 5)) return B();

    return C();
}

bool B()
{
    // B -> 2B | 1A3AC

    if(V[step] == 2)    {
        ++step;
        if(step <= N)   return B();
    }

    if(V[step] == 1 && V[step + 2] == 3 && step + 4 <= N)   {
        step += 4;
        return C();
    }

    return 0;
}

bool C()
{
    // C -> 2 | 3BC | 12A

    if(V[step] == 2 && step <= N)   {
        ++step;
        return 1;
    }

    if(V[step] == 3)    {
        ++step;
        if(B() && step <= N)    return C();
    }

    if(V[step] == 1 && V[step + 1] == 2 && step + 2 <= N)    {
        step += 3;
        return 1;
    }

    return 0;
}

int main()
{
    ifstream f(iname);  ofstream g(oname);

    f >> T;

    for(int t = 1; t <= T; ++t) {
        f >> N;
        V.push_back(-1);

        for(int i = 1, x; i <= N; ++i)  {
            f >> x;
            V.push_back(x);
        }

        step = 1;
        g << A() << '\n';

        V.clear();
    }

    g.close();
    return 0;
}