#include <iostream>
#include <fstream>

using std::cout;

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

int len;
int arrIt;
int arrLen;
int arr[10005];

void b();

void c();

int main() {
    fin >> len;
    for (int iter = 0; iter < len; ++iter) {
        fin >> arrLen;
        for (int it = 0; it < arrLen; ++it) {
            fin >> arr[it];
        }
        if (arrLen == 1) {
            fout << "1\n";
        } else {
            arrIt = 0;
            b();
            if (arrIt == arrLen - 1) {
                fout << "1\n";
            } else {
                fout << "0\n";
            }
        }
    }
    return 0;
}

void b() {
    if (arr[arrIt] == 2) {
        arrIt++;
        b();
    } else {
        if (arrIt + 4 < arrLen)
            if (arr[arrIt] == 1 && arr[arrIt + 1] <= 3 && arr[arrIt + 2] == 3 && arr[arrIt + 3] <= 3) {
                arrIt += 4;
                c();
            }
    }
}

void c() {
    if (arr[arrIt] == 2) {
        arrIt++;
    } else if (arr[arrIt] == 3) {
        arrIt++;
        b();
        c();
    } else if (arrIt + 2 < arrLen) {
        if (arr[arrIt] == 1 && arr[arrIt + 1] == 2 && arr[arrIt + 2] <= 3) {
            arrIt += 2;
        }
    }
}