#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,counter=0,exist=0,k;
    if(length==3 && a[0]==1 && a[1]==2)
        return(1);
    if(length==1)
        return(1);
    if(a[0]==3)
    {
        counter++;
        i++;
    }
    while(i<length)
    {

        while(a[i]==2)
            i++;
        if(a[i]!=1 || a[i+2]!=3)
            return(0);
        i+=4;
        if(i>=length)
            return(0);
        if(a[i]==3)
        {
            counter++;
            i++;
        }
        else
            break;
    }
    i--;
        for(k=0;k<counter+1;k++)
        {
            i++;
            if(i>=length)
                return(0);
            if(a[i]==2)
            {
                if(i>=length)
                    return(0);
                continue;
            }
            if(a[i]==1 && a[i+1]==2 && 1<=a[i+2] && a[i+2]<=3)
            {
                i+=2;
                if(i>=length)
                    return(0);
                continue;
            }
            return(0);
        }

return(1);

}
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";
    }
}