#include <bits/stdc++.h>

using namespace std;

const int L_MAX = 1e4 + 5;
unsigned int N, L;
short int expr[L_MAX];
unsigned int pos;

void SetInput(string name)
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    (void)!freopen((name + ".in").c_str(), "r", stdin);
    (void)!freopen((name + ".out").c_str(), "w", stdout);
}

bool CanTransformInA()
{
    if(pos >= L) return false;

    if(expr[pos] == 1 || expr[pos] == 2 || expr[pos] == 3)
        return true;

    return false;
}

bool CanTransformInC();

bool CanTransformInB()
{
    if(pos >= L) return false;

    if(expr[pos] == 2)
    {
        pos++; /// Sarim peste '2'
        return CanTransformInB();
    }

    if(expr[pos] == 1)
    {
        pos++; /// Sarim peste '1'
        if(not CanTransformInA()) return false;
        pos++; /// Sarim peste 'A'
        if(pos >= L || expr[pos] != 3) return false;
        pos++; /// Sarim peste '3'
        if(not CanTransformInA()) return false;
        pos++; /// Sarim peste 'A'
        return CanTransformInC();
    }
    return false;
}

bool CanTransformInC()
{
    if(pos >= L)
        return false;

    if(expr[pos] == 2)
        return true;

    if(expr[pos] == 3)
    {
        pos++; /// Sarim peste '3'
        if(not CanTransformInB()) return false;
        pos++; /// Sarim peste 'B'
        return CanTransformInC();
    }

    if(expr[pos] == 1)
    {
        pos++; /// Sarim peste '1'
        if(pos >= L || expr[pos] != 2) return false;
        pos++; /// Sarim peste '2'
        return CanTransformInA();
    }

    return false;
}

void Solve()
{
    pos = 0;
    if(CanTransformInA() && pos == L - 1)
    {
        cout << "1\n";
        return;
    }

    pos = 0;
    if(CanTransformInB() && pos == L - 1)
    {
        cout << "1\n";
        return;
    }

    pos = 0;
    if(CanTransformInC() && pos == L - 1)
    {
        cout << "1\n";
        return;
    }

    cout << "0\n";
}

void ReadInput()
{
    cin >> N;

    while(N--)
    {
        cin >> L;
        for(unsigned int i = 0; i < L; i++)
            cin >> expr[i];
        Solve();
    }
}

int main()
{
    SetInput("perle");

    ReadInput();

    return 0;
}