#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) {
                fout << "1\n";
            } else {
                arrIt = 0;
                c();
                if (arrIt == arrLen)
                    fout << "1\n";
                else
                    fout << "0\n";
            }
        }
    }
    return 0;
}

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

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