#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("perle.in");
ofstream fout("perle.out");

int n, a[10002], k, j;

void citire(){
    fin >> k;
    for(int i = 1; i <=k; i++){
        fin >> a[i];
    }
}
void zerozare()
{
    for(int i=1; i<=k; i++)
        a[i]=0;
    k=0;
    j=0;
}
int A(int i)
{
    j=i;
    if(i==k)
        return 1;
    return 0;
}
int B(int i);
int C(int i)
{
    if(i>k)
        return 0;
    if(a[i]==2)
    {
        j=i;
        if(i==k)
            return 1;
    }    
    if(a[i]==1 && a[i+1]==2)
        return A(i+2);
    if(a[i]==3)
    {
        B(i+1);
        return C(j+1);
    }   
    return 0;
}
int B(int i)
{
    if(i>k)
        return 0;
    if(a[i]==2)
        return B(i+1);
    if(a[i]==1 && a[i+2]==3)
        return C(i+4);
    return 0;
}

bool perle()
{
    if(k == 1)
        return 1;
    if(a[1]==1 || a[1]==2)
        if(B(1)==1)
            return 1;
    if(C(1)==1)
        return 1;
    return 0;
}

int main()
{
    fin >> n;
    for(int i = 0; i < n; i++)
    {
        citire();
        fout << perle() << '\n';
        zerozare();
    }
    return 0;
}