#include <iostream>
#include <fstream>
#include <stack>
using namespace std;
#define MAX 10002
ifstream in("perle.in");
ofstream out("perle.out");
int v[MAX];
stack <int> S;
stack <int> necesar;
int fix[MAX];
int main()
{
    int n,m,i,j,k,lmax,x,t;
    in>>k;
    for(i=1; i<=k; i++)
    {
        in>>lmax;
        for(j=1; j<=lmax; j++)
            in>>v[j];
        if(lmax==1)out<<1<<'\n';
        else
        {
            int l=1;
            int poz=0;
            t=1;
            if(v[1]==2)
            {
                S.push(5);
                l=2;
            }
            if(v[1]==3)
            {
                S.push(6);
                S.push(5);
                l=3;
            }
            if(v[1]==1&&v[3]==3)
            {
                S.push(6);
                l=5;
            }
            if(v[1]==1&&v[3]!=3)
                t=0;

            poz=l;
            if(v[1]==3)poz=2;
           while(!S.empty()&&(l<lmax&&t))
                {
                    x=S.top();
                    S.pop();

                    if(x==5)
                    {   int nt=1;
                        if(v[poz]==2)
                        {
                            ++l;
                            ++poz;
                            S.push(5);
                            nt=0;
                        }
                        if(v[poz]==3&&nt)
                        {  nt=0;
                            t=0;

                        }
                        if(v[poz]==1&&v[poz+2]==3&&nt)
                        {   nt=0;
                            S.push(6);
                            l=l+4;
                            poz+=4;

                        }
                        if(v[poz]==1&&v[poz+2]!=3&&nt&&S.top()!=6)
                            t=0;
                    }
                    int nt=1;
                    if(x==6)
                    {
                        if(v[poz]==3)
                    {
                        S.push(6);
                        S.push(5);
                        poz=poz+1;
                        l=l+2;
                        nt=0;
                    }
                    if(v[poz]==1&&v[poz+1]==2&&nt)
                    {
                        l=l+2;
                        poz=poz+3;
                        nt=0;
                    }
                    if(v[poz]==1&&v[poz+1]!=2&&nt)
                    {
                        t=0;
                        nt=0;
                    }
                    if(v[poz]==2&&nt)
                        ++poz;
                    }

                }
                int imp=0;
                int tor=0;
                int bla=0;
                if(S.empty())bla=1;
                if(!S.empty()&&v[lmax]==2)tor=1;
            while(!S.empty()&&tor)
               {
                   int x=S.top();
                   if(x==6)++imp;
                   else {tor=0; break;}
                   S.pop();
               }
               if(tor&&imp)
                for(int lim=lmax;lim>=lmax-imp+1;lim--)
                if(v[lim]!=2)tor=0;
            if(t&&(bla||tor))out<<1<<'\n';
            else out<<0<<'\n';
            while(!S.empty())
                S.pop();


        }

    }

    return 0;
}