#include <iostream>

#include <fstream>

using namespace std;

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

const int A=4, B=5, C=6;
int n, lg, st[20000], v[10001];

int verif(int n, int v[], int st[])
{
    int vf = 1;
    for(int i=1; i<=n; i++)
    {
        if(vf == 0)
            return 0;
        else if(st[vf] < 4)
        {
            if(v[i] != st[vf])
                return 0;
            else
                vf--;
        }
        else if(st[vf] == A)
            --vf;
        else if(st[vf] == B)
        {
            if(v[i] == 1)
            {
                st[vf] = C;
                st[vf+1] = A;
                st[vf+2] = 3;
                st[vf+3] = A;
                vf+=3;
            }
            if(v[i] == 3)
                return 0;
        }
        else if(st[vf] == C)
        {
            if(v[i] == 1)
            {
                st[vf] = A;
                st[vf+1] = 2;
                vf++;
            }
            if(v[i] == 2)
                --vf;
            if(v[i] == 3)
            {
                st[vf+1] = B;
                ++vf;
            }
        }
    }
    if(vf>0) return 0;
    return 1;
}

int main()
{
    in>>n;
    for(int i=1; i<=n; i++)
    {
        in>>lg;
        for(int j=1; j<=lg; j++)
            in>>v[j];

        int ok = 0;
        for(int j=A ; j<=C ; j++)
        {
            st[1] = j;
            if(verif(lg, v, st))
                ok = 1;
        }
        out<<ok<<'\n';
    }
    return 0;
}