#include <fstream>
#include <cstdlib>
#include <iostream>
#include <vector>
#define N 10001
using namespace std;
int A[N];
int n;
int matchesC(int);
// Returns the last position of a matching B starting at position a
int matchesB(int a) {
    if (a >= n)
        return n + 1;
    if (A[a] == 2)
        return matchesB(a + 1);
    if (n - a + 1 >= 5 && A[a] == 1 && A[a + 2] == 3)
        return matchesC(a + 4);
    return n + 1;
}
// Returns the last position of a matching C starting at position a
int matchesC(int a) {
    if (a > n)
        return n + 1;
    if (A[a] == 2)
        return a;
    int len = n - a + 1;
    if (len >= 3 && A[a] == 1 && A[a + 1] == 2)
        return a + 2;
    if (len >= 7 && A[a] == 3)
        return matchesC(matchesB(a + 1) + 1);
    return n + 1;
}

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

    int t;
    fin >> t;
    while (t--) {
        fin >> n;
        if (n == 1) {
            fout << 1 << "\n";
            fin >> n;
        }
        else {
            for (int i = 1; i <= n; ++i)
                fin >> A[i];
            fout << (matchesB(1) == n || matchesC(1) == n) << "\n";
        }
    }

    return 0;
}