#include <fstream>
#include <iomanip>
#include <string>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#include <map>
#include <string.h>
#include <queue>
#include <stack>

#define INF 0x3f3f3f3f

using namespace std;

#ifdef DEBUG
string name = "data";
#else
string name = "perle";
#endif

ifstream fin(name + ".in");
ofstream fout(name + ".out");

int t;
int n;
int s[10001];

int possible(int i, int target) {
    if (i >= n) {
        return -1;
    }
    
    if (target == 4 && i == (n - 1)) {
        return (n - 1);
    }
    
    if ((target == 2 || target == 4) && s[i] == 2) {
        return possible(i + 1, 2);
    }
    
    if ((target == 2 || target == 4)) {
        if ((n - i) >= 5) {
            if (s[i] == 1 && s[i + 2] == 3) {
                return possible(i + 4, 3);
            }
        }
    }
    
    if (target == 3 && s[i] == 2) {
        return i;
    }
    
    if ((target == 3 || target == 4) && (n - i) >= 3 && s[i] == 1 && s[i + 1] == 2) {
        return i + 2;
    }
    
    if ((target == 3 || target == 4) && (n - i) > 3 && s[i] == 3) {
        int ndx = possible(i + 1, 2);
        if (ndx == -1) {
            return -1;
        }
        return possible(ndx + 1, 3);
    }
    
    return -1;
}

void solve() {
    fin >> n;
    for (int i = 0; i < n; ++i) {
        fin >> s[i];
    }
    
    fout << (possible(0, 4) == (n - 1)) << "\n";
}

int main() {
    
    fin >> t;
    while (t > 0) {
        t--;
        solve();
    }
    
    return 0;
}