#include<fstream>
using namespace std;
ifstream f("perle.in");
ofstream g("perle.out");
struct Used{
int val;
int used;
};
Used a[11000];
int sy,rc=1,length=0;
void C();
void B();
void read_number(int& n)
{
    f>>n;
}
void read_array()
{
    int i;
    f>>length;
    for(sy=0;sy<length;sy++)
    {
        f>>a[sy].val;
        a[sy].used=0;
    }
}
int ink()
{
    if(sy>=length)
        return(1);
    else
        return(0);
}
int is(int x)
{
    if(a[sy].val==x)
    {
        if(ink()==1)
            return(0);
        else
            return(1);
    }
    else
    {
        return(0);
    }
}
void A()
{
    if(!is(1) && !is(2) && !is(3))
       rc=0;
}
void B()
{
    if(is(2))
    {
        a[sy].used=1;
        sy++;
        a[sy].used=1;
        B();
        return;
    }
    if(is(1))
    {
        a[sy].used=1;
        sy++;
        A();
        a[sy].used=1;
        sy++;
        if(!is(3))
        {
            rc=0;
            return;
        }
        a[sy].used=1;
        sy++;
        A();
        a[sy].used=1;
        sy++;
        a[sy].used=1;
        C();
        return;
    }
    if(sy!=0 && !is(1) && !is(2))
        rc=0;
}
void C()
{
    if(is(2))
    {
        a[sy].used=1;
        if(sy<length-1)
            sy++;
        return;
    }
    if(is(1))
    {
        a[sy].used=1;
        sy++;
        if(!is(2))
        {
           rc=0;
           return;
        }
        a[sy].used=1;
        sy++;
        a[sy].used=1;
        A();
        if(sy<length-1)
            sy++;
            return;
    }
    if(is(3))
    {
        a[sy].used=1;
        sy++;
        a[sy].used=1;
        B();
        sy++;
        a[sy].used=1;
        C();
        sy++;
        a[sy].used=1;
        return;
    }
    if(sy==0)
        rc=0;
}
int check()
{
    sy=0;
    rc=1;
    if(length==1)
    {
        A();
        return(rc);
    }
    if(length==3)
    {
        C();
        if(sy!=length-1)
            return(0);
        return(rc);
    }
    if(a[0].val==2 || a[0].val==1)
    {
        B();
        if(a[sy].used==0)
            return(0);
        return(rc);
    }
    if(a[0].val==3)
    {
        C();
        if(a[sy].used==0)
            return(0);
        return(rc);
    }
}
int main()
{
    int n,i;
    read_number(n);
    for(i=0;i<n;i++)
    {
        read_array();
        g<<check()<<"\n";
    }
}