#include<fstream>
using namespace std;
ifstream f("perle.in");
ofstream g("perle.out");
void read_number(int& x)
{
    f>>x;
}
void read_array(int& length, int a[])
{
    int i;
    f>>length;
    for(i=0;i<length;i++)
        f>>a[i];
}
int switch_B(int& i,int length, int a[])
{
    while(a[i]==2)
        i++;
    if(i+4>=length)
        return(0);
    if(a[i]!=1 || a[i+2]!=3)
        return(0);
    i+=4;
    return(1);
}
int switch_C(int i,int length,int a[])
{
    if(length-i==1 && a[i]==2)
        return(2);
    if(length-i==3 && a[i]==1 && a[i+1]==2)
        return(2);
    if(a[i]==3)
        return(1);
    i++;
    return(0);
}
int check(int length, int a[])
{
    int i=0,current_nb=0;
    if(length==3 && a[0]==1 && a[1]==2)
        return(1);
    if(length==1)
        return(1);
    if(a[0]==2 || a[0]==1)
       while(i<length)
       {
           int d;
           if(switch_B(i,length,a)==0)
                return(0);
           d=switch_C(i,length,a);
             if(d==2)
                return(1);
             if(d==0)
                return(0);
       }
    if(a[0]==3)
        while(i<length)
        {
             int d=switch_C(i,length,a);
             if(d==2)
                return(1);
             if(d==0)
                return(0);
              if(switch_B(i,length,a)==0)
                return(0);
             d=switch_C(i,length,a);
             if(d==2)
                return(1);
             if(d==0)
                return(0);

        }
    return(0);
}
int main()
{
    int i,n,a[11000],length;
    read_number(n);
    for(i=0;i<n;i++)
    {
        read_array(length,a);
        g<<check(length,a)<<"\n";
    }
}