#include <bits/stdc++.h>

using namespace std;

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

vector<int> s;

bool parse_A(int& idx);
bool parse_B(int& idx);
bool parse_C(int& idx);

bool parse_A(int& idx) {
    if(idx >= s.size()) return false;
    if(s[idx] == 1 || s[idx] == 2 || s[idx] == 3) {
        idx++;
        return true;
    }
    return false;
}

bool parse_B(int& idx) {
    if(idx >= s.size()) return false;
    if(s[idx] == 2) {
        idx++;
        return parse_B(idx);
    }
    if(s[idx] == 1) {
        idx++;
        if(!parse_A(idx)) return false;
        if(idx >= s.size() || s[idx] != 3) return false;
        idx++;
        if(!parse_A(idx)) return false;
        if(!parse_C(idx)) return false;
        return true;
    }
    return false;
}

bool parse_C(int& idx) {
    if(idx >= s.size()) return false;
    if(s[idx] == 2) {
        idx++;
        return true;
    }
    if(s[idx] == 3) {
        idx++;
        if(!parse_B(idx)) return false;
        if(!parse_C(idx)) return false;
        return true;
    }
    if(s[idx] == 1) {
        idx++;
        if(idx >= s.size() || s[idx] != 2) return false;
        idx++;
        if(!parse_A(idx)) return false;
        return true;
    }
    return false;
}

void solve() {
    int l;
    fin >> l;
    s.resize(l);
    for(int i = 0; i < l; ++i) {
        fin >> s[i];
    }
    
    int idx = 0;
    bool ok = false;
    
    idx = 0;
    if(parse_A(idx) && idx == l) ok = true;
    
    if(!ok) {
        idx = 0;
        if(parse_B(idx) && idx == l) ok = true;
    }
    
    if(!ok) {
        idx = 0;
        if(parse_C(idx) && idx == l) ok = true;
    }
    
    fout << (ok ? 1 : 0) << "\n";
}

int main() {
    int t;
    fin >> t;
    for(; t; --t) {
        solve();
    }
    
    fin.close();
    fout.close();
    return 0;
}