#include <fstream>
#include <stack>
using namespace std;

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

long m,n,i,j,x,d,valid[2];
stack <int> st[2];


int main()
{
    f>>n;
    for (i=1;i<=n;i++)
    {
        f>>m;
        if (m==1)
        {
            f>>x;
            g<<"1\n";
            continue;
        }
        st[0].push(5);
        st[1].push(6);
        valid[0]=valid[1]=1;
        while (m!=0)
        {
            f>>x;
            m--;
            for (j=0;j<2;j++)
            {
                if (valid[j]==1)
                {
                    if (st[j].top()<=3)
                    {
                        if (x!=st[j].top())
                            valid[j]=0;
                        st[j].pop();
                        continue;
                    }
                    if (st[j].top()==4)
                    {
                        st[j].pop();
                        continue;
                    }
                    if (st[j].top()==5)
                    {
                        if (x==3)
                            valid[j]=0;
                        else if (x==1)
                        {
                            st[j].pop();
                            st[j].push(6);
                            st[j].push(4);
                            st[j].push(3);
                            st[j].push(4);
                        }
                        continue;
                    }
                    if(x==1)
                    {
                        st[j].pop();
                        st[j].push(4);
                        st[j].push(2);
                        continue;
                    }
                    if (x==2)
                    {
                        st[j].pop();
                        continue;
                    }
                    st[j].push(5);
                    st[j].push(3);
                }
            }
            if (st[0].empty() && m)
                valid[0]=0;
            if (st[1].empty() && m)
                valid[1]=0;
        }
        g<<((st[0].empty() && valid[0]) || (st[1].empty() && valid[1]))<<"\n";
        while (!st[0].empty())
            st[0].pop();
        while (!st[1].empty())
            st[1].pop();
    }

    return 0;
}