#include <fstream>
#include <algorithm>
using namespace std;

ifstream fin("perle.in");
ofstream fout("perle.out");

const int MAX_N = 10100;

int v[MAX_N];

bool checkB(int, int);
bool checkC(int, int);

bool checkB(int x, int y) {
    if(y - x + 1 < 5) {
        return false;
    }
    if(v[x] == 2 && checkB(x + 1, y)) {
        return true;
    }
    if(v[x] == 1 && v[x + 2] == 3 && checkC(x + 4, y)) {
        return true;
    }
    return false;
}

bool checkC(int x, int y) {
    if(x == y && v[x] == 2) {
        return true;
    }
    if(v[x] == 3) {
        for(int i = x + 1; i < y; i++) {
            if(checkB(x + 1, i) && checkC(i + 1, y)) {
                return true;
            }
        }
    }
    if(v[x] == 1 && v[x + 1] == 2 && y - x + 1 == 3) {
        return true;
    }
    return false;
}

int main() {
    int n;
    fin >> n;
    for(int i = 1; i <= n; i++) {
        fin >> v[0];
        for(int j = 1; j <= v[0]; j++) {
            fin >> v[j];
        }
        if(v[0] == 1 || checkB(1, v[0]) || checkC(1, v[0])) {
            fout << "1\n";
        }
        else {
            fout << "0\n";
        }
    }
    return 0;
}