#include <fstream>

using namespace std;

ifstream cin("perle.in");
ofstream cout("perle.out");

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;
}