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

using namespace std;

int A[N];
bool RB[N][N], HB[N][N], RC[N][N], HC[N][N];;

bool matchesC(int, int);
 
bool matchesB(int a, int b) {
    if (HB[a][b])
        return RB[a][b];
    #if (DEBUG)
        cout << "matchesB(" << a << ", " << b << ")\n";
    #endif
    HB[a][b] = 1;
    if (a >= b) // RB[a][b] = 0 is already the case here
        return 0;
    if (A[a] == 2) {
        bool res = matchesB(a + 1, b); 
        RB[a][b] = res;
        return res;
    }
    if (b - a + 1 >= 5 && A[a] == 1 && A[a + 2] == 3) {
        bool res = matchesC(a + 4, b);
        RB[a][b] = res;
        return res;
    }
    return 0;
}

bool matchesC(int a, int b) {
    if (HC[a][b])
        return RC[a][b];
    #if (DEBUG)
        cout << "matchesC(" << a << ", " << b << ")\n";
    #endif
    HC[a][b] = 1;
    if (a > b)
        return 0; // RC[a][b] == 0 is already the case here
    int len = b - a + 1;
    if (len == 1 && A[a] == 2
            || len == 3 && A[a] == 1 && A[a + 1] == 2) {
        RC[a][b] = 1;
        return 1;
    }
    if (len >= 7 && A[a] == 3)
        for (int i = a + 2; i <= b; ++i)
            if (matchesB(a + 1, i)) {
                if (HC[i + 1][b])
                    return RC[i + 1][b];
                int res = matchesC(i + 1, b);
                RC[a][b] = res;
                return res;
            }
    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)
                    RB[i][j] = RC[i][j] = HB[i][j] = HC[i][j] = 0;
        }
    }

    return 0;
}