#include <fstream>
ifstream cin("perle.in");
ofstream cout("perle.out")
using namespace std;

int main()
{
    cout << "Hello world!" << endl;
    return#include <iostream>
using namespace std;
const int A = 4, B = 5, C = 6, MAX = 10001;
int v[MAX], n, st[MAX], vf, t;
int verif(int pm) {
    vf = 1;
    st[vf] = pm;
    for(int i = 1; i <= n; ++i) {
        if(vf == 0) {
            return 0;
        }
        if(st[vf] < 4 && st[vf] != v[i]) {
            return 0;
        }
        if(st[vf] == A) {
            --vf;
        } else if(st[vf] == B) {
            if(v[i] == 3) {
                return 0;
            } else if(v[i] == 1) {
                st[vf] = C;
                st[vf + 1] = A;
                st[vf + 2] = 3;
                st[vf + 3] = A;
                vf = vf + 3;
            }
        } else if(st[vf] == C) {
            ///perla normala v[i]
            if(v[i] == 1) {
                st[vf] = A;
                st[ ++vf ] = 2;
            } else if(v[i] == 2) {
                --vf;
            } else {
                st[ ++vf ] = B;
            }
        } else {
            --vf;
        }
    }
    if(vf > 0) {
        return 0;
    }
    return 1;
}
int main()
{
    cin >> t;
    while(t--) {
        cin >> n;
        for(int i = 1; i <= n; ++i) {
            cin >> v[i];
        }
        int ok = 0;
        if(verif(A) == 1) { ok = 1; }
        if(verif(B) == 1) { ok = 1; }
        if(verif(C) == 1) { ok = 1; }
        cout << ok << '\n';
    }
    return 0;
} 0;
}