#include<cstdio>
using namespace std;
FILE *f,*g;
int t,n,i,v[10009];
int c(int );
int b(int l)
{
    if(l>n)
    return -100000;
    if(v[l]==2)
    return 1+b(l+1);
    if(v[l]==1&&v[l+2]==3)
    return 4+c(l+4);
    return -100000;
}
int c(int l)
{
    if(l>n)
    return 0;
    if(v[l]==2)
    return 1;
    if(v[l]==3)
    {
        int k=b(l+1);
        if(k>0)
        return k+1+c(k+1+l);
    }
    if(v[l]==1&&v[l+1]==2)
    return 3;
    return 0;
}
int main()
{
    f=fopen("perle.in","r");
    g=fopen("perle.out","w");
    fscanf(f,"%d",&t);
    while(t)
    {
        --t;
        fscanf(f,"%d",&n);
        for(i=1;i<=n;++i)
        fscanf(f,"%d",&v[i]);
        if(n==1)
        fprintf(g,"1");
        else
        if(b(1)==n||c(1)==n)
        fprintf(g,"1");
        else
        fprintf(g,"0");
        fprintf(g,"\n");
    }
    return 0;
}