#include <bits/stdc++.h>
using namespace std;

int sirag[10001];

int testA(int left, int right);
int testB(int left, int right);
int testC(int left, int right);

int testA(int left, int right)
{
    return right - left == 1;
}

int testB(int left, int right)
{
    while (left < right && sirag[left] == 2)
        left++;
    if (right - left >= 5 && sirag[left] == 1 && sirag[left+2] == 3)
        return testC(left + 4, right);
    return 0;
}

int testC(int left, int right)
{
    switch (sirag[left])
    {
    case 1:
        return right - left == 3 && sirag[left+1] == 2;
    case 2:
        return right - left == 1;
    case 3:
        if (right - left < 7 || sirag[left+1] == 3)
            return 0;
        for (int i = left + 6; i < right; i++)
            if (testB(left + 1, i) && testC(i, right))
                return 1;
        return 0;
    default:
        return 0;
    }
}

int test(int len)
{
    return testA(0, len) || testB(0, len) || testC(0, len);
}

int main()
{
    ifstream in("perle.in");
    ofstream out("perle.out");
    //istream &in = cin;
    //ostream &out = cout;

    int n;
    in >> n;
    while (--n >= 0)
    {
        int len;
        in >> len;
        for (int i = 0; i < len; i++)
            in >> sirag[i];
        out << test(len) << endl;
    }
}