#include <iostream>
#include <fstream>
#include <queue>
#include <iomanip>
#include <unordered_map>
using namespace std;
int n, a[100005];
string s;
int i = 0;

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

bool A();
bool B();
bool C();
bool A()
{
    if (i == n + 1)
        return false;
    if (a[i] == 1 || a[i] == 2 || a[i] == 3)
    {
        i++;
        return true;
    }
    else
    {
        return false;
    }
}

bool B() {
    if (i == n + 1)
        return false;
    if (a[i] == 2)
    {
        i++;
        return B();
    }
    else if (a[i] == 1) {
        i++;
        bool ok = A();
        if (!ok)
            return false;
        if (a[i] != 3)
            return false;
        i++;
        ok = A();
        if (!ok)
            return false;
        return C();
    }
    return false;
}
bool C()
{
    if (i == n + 1)
        return false;
    if (a[i] == 2)
    {
        i++;
        return true;
    }
    else if (a[i] == 3)
    {
        i++;
        bool ok = B();
        if (!ok)
            return false;
        return C();
    }
    else if (a[i] == 1 && a[i + 1] == 2)
    {
            i += 2;
            return A();
    }
    return false;
}




void solve()
{
    f >> n;
    for (int i = 1; i <= n; i++)
        f >> a[i];
    i = 1;
    if (A() && i == n + 1)
    {
        g << 1 << '\n';
        return;
    }

    i = 1;
    if (B() && i == n + 1)
    {
        g << 1 << '\n';
        return;
    }

    i = 1;
    if (C() && i == n + 1)
    {
        g << 1 << '\n';
        return;
    }
    g << 0 << '\n';
}
int main()
{
    int t;
    f >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}