#include <fstream>
#include <vector>

using namespace std;

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

int i;
int n;
vector<int> a;

bool A();
bool B();
bool C();

void test_case()
{
    cin >> n;
    a.resize(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    bool sol = false;

    i = 1;
    bool rez = A();
    if (rez == 1 && i == n + 1)
        sol = true;

    i = 1;
    rez = B();
    if (rez == 1 && i == n + 1)
        sol = true;

    i = 1;
    rez = C();
    if (rez == 1 && i == n + 1)
        sol = true;
    cout << sol << '\n';
}

int main()
{
    int T;
    cin >> T;

    while (T--)
        test_case();

    return 0;
}

bool A()
{
    if (i == n + 1)
        return 0;

    if (a[i] == 1 || a[i] == 2 || a[i] == 3)
    {
        i++;
        return 1;
    }

    return 0;
}

bool B()
{
    if (i == n + 1)
        return 0;

    if (a[i] == 2)
    {
        i++;
        return B();
    }

    if (a[i] == 1)
    {
        i++;
        bool rez = A();
        if (rez == 0)
            return 0;

        if (a[i] != 3)
            return 0;
        i++;

        rez = A();
        if (rez == 0)
            return 0;

        rez = C();
        if (rez == 0)
            return 0;
        return 1;
    }

    return 0;
}

bool C()
{
    if (i == n + 1)
        return 0;

    if (a[i] == 2)
    {
        i++;
        return 1;
    }

    if (a[i] == 3)
    {
        i++;

        bool rez = B();
        if (rez == 0)
            return 0;

        rez = C();
        if (rez == 0)
            return 0;
        return 1;
    }

    if (a[i] == 1)
    {
        i++;
        if (a[i] != 2)
            return 0;

        i++;
        bool rez = A();
        if (rez == 0)
            return 0;
        return 1;
    }

    return 0;
}