#include <fstream>
#include <cstdlib>
#include <iostream>
#include <vector>
#define N 10001

using namespace std;

int A[N];
bool R[N][N], H[N][N];

bool matchesC(int, int);
 
bool matchesB(int a, int b) {
    if (H[a][b])
        return R[a][b];
    #if (DEBUG)
        cout << "matchesB(" << a << ", " << b << ")\n";
    #endif
    H[a][b] = 1;
    if (a >= b) {
        R[a][b] = 0;
        return 0;
    }
    if (A[a] == 2) {
        bool res = matchesB(a + 1, b); 
        R[a][b] = res;
        return res;
    }
    if (b - a + 1 >= 5 && A[a] == 1 && A[a + 2] == 3) {
        bool res = matchesC(a + 4, b);
        R[a][b] = res;
        return res;
    }
    return 0;
}

bool matchesC(int a, int b) {
    #if (DEBUG)
        cout << "matchesC(" << a << ", " << b << ")\n";
    #endif
    if (a > b)
        return 0;
    int len = b - a + 1;
    if (len == 1 && A[a] == 2
        || len == 3 && A[a] == 1 && A[a + 1] == 2)
        return 1;
    if (len >= 7 && A[a] == 3)
        for (int i = a + 2; i <= b; ++i)
            if (matchesB(a + 1, i))
                return matchesC(i + 1, b);
    return 0;
}
 
int main() {
    ifstream fin("perle.in");
    ofstream fout("perle.out");
    
    int t;
    fin >> t;
    while (t--) {
        int n;
        fin >> n;
        if (n == 1) {
            fout << 1 << "\n";
            fin >> n;
        }
        else {
            for (int i = 1; i <= n; ++i)
                fin >> A[i];
            bool res =  (matchesB(1, n) || matchesC(1, n));
            fout << res << "\n";
            #if (DEBUG)
                cout << res << "\n";
            #endif
            for (int i = 1; i <= n; ++i)
                for (int j = 1; j <= n; ++j)
                    R[i][j] = H[i][j] = 0;
        }
    }

    return 0;
}