#include <iostream>
#include <fstream>
using namespace std;
ifstream in("perle.in");
ofstream out("perle.out");
const int A=4,B=5,C=6;
int verif(int n,int v[],int st[])
{
    int vf=1;
    for(int i=1; i<=n; ++i)
    {
        if(vf==0) return 0;
        if(st[vf]<4)
        {
            if(st[vf]==v[i])
                --vf;
            else return 0;
        }
        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=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;
    else return 1;

}
int main()
{
    int n,st[20000],v[20000];
    in>>n;
    for(int i=1; i<=n; ++i)
    {
        int lg;
        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;
}