#include <stdio.h>
#define FOR(i,a,b) for(i=a;i<=b;++i)
#define MAXL 10010

int n,i,j,l,nc;
int v[MAXL];

bool p_a(int);
bool p_b(int);
bool p_c(int);

bool p_a(int x)
{
     if ((x == l) && (!nc)) return true;
     if ((nc) && (x < l)) return p_c(x+1);
     return false;
}

bool p_b(int x)
{
     if ((v[x] == 2) && (x < l)) return p_b(x+1);
     if ((v[x] == 1) && (v[x+2] == 3) && (x+3 < l)) return p_c(x+4);
     return false;
}

bool p_c(int x)
{
     if ((v[x] == 2) && (x == l) && (!nc)) return true;
     if ((v[x] == 2) && (x < l) && (nc))
     {
        nc--;
        return p_c(x+1);
     }
     if ((v[x] == 3) && (x < l)) 
     {
        nc++;
        return p_b(x+1);
     }
     if ((v[x] == 1) && (v[x+1] == 2) && (x == l-2)) return true;
     if ((v[x] == 1) && (v[x+1] == 2) && (x+2 < l) && (nc)) 
     {
        nc--;
        return p_c(x+3);
     }
     return false;
}

int check()
{
    if (p_a(1)) return 1;
    nc = 0;
    if (p_b(1)) return 1;
    nc = 0;
    if (p_c(1)) return 1;
    nc = 0;
    return 0;
}

int main()
{
    freopen("perle.in","r",stdin);
    freopen("perle.out","w",stdout);
    
    scanf("%d\n",&n);
    FOR (i,1,n)
    {
        scanf("%d ",&l);
        FOR (j,1,l) scanf("%d ",&v[j]);
        scanf("\n");
        printf("%d\n",check());
    }
    
    return 0;
}