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

using namespace std;

bool A[N][N][20];
short int B[N];
const int T[4][4] = {
    { 0 },
    { 1, 5, 0 },
    { 1, 3, 4, 0 },
    { 1, 6, 0 }
};
const int R[9][3] = {
    { 4, 2, 2 },
    { 5, 7, 2 }, 
    { 1, 8, 7 },
    { 6, 9, 8 },
    { 1, 3, 9 },
    { 6, 10, 3 },
    { 5, 11, 3 },
    { 2, 3, 10 },
    { 4, 1, 11 }
};

bool isValid(int n) {
    // Initialize table
    for (int i = 1; i <= n; ++i)
        for (int j = 0; T[B[i]][j] != 0; ++j)
            A[1][i][T[B[i]][j]] = 1;

    for (int i = 2; i <= n; ++i)
        for (int j = 1; j <= n - i + 1; ++j)
            for (int k = 1; k <= i - 1; ++k)
                for (int l = 0; l < 9; ++l)
                    if (A[k][j][R[l][0]] && A[i - k][j + k][R[l][1]])
                        A[i][j][R[l][2]] = 1;

    bool res = A[n][1][1] || A[n][1][2] || A[n][1][3]; 

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            for (int l = 0; l < 9; ++l)
                A[i][j][l] = 0;

    return res;
}

int main() {
    ifstream fin("perle.in");
    ofstream fout("perle.out");
    
    int t;
    fin >> t;
    while (t--) {
        int n;
        fin >> n;
        for (int i = 1; i <= n; ++i)
            fin >> B[i];
        fout << isValid(n) << "\n";
    }

    return 0;
}