#include <cstdio>
using namespace std;
const int maxn = 10011;
short v[maxn];
int l;
int pos;
bool c();
bool b()
{

    if(v[pos] == 2)
    {
        ++pos;
        return b();
    }
    if(v[pos] == 1 && v[pos+2] == 3)
    {
        pos+=4;
        return c();
    }
    return 0;
}

bool c()
{
    if(l == pos && v[pos] == 2)
        return 1;
    if(pos == l - 2 && v[pos] == 1 && v[pos+1] == 2)
        return 1;
    if(v[pos] == 3)
    {
        ++pos;
        return (b() && c());
    }
    return 0;
}

int main()
{
    int n;
    freopen("perle.in","r",stdin);
    freopen("perle.out","w",stdout);
    setvbuf(stdin,NULL,_IOFBF,1024);
    scanf("%d",&n);
    int i;
    while(n--)
    {
        scanf("%d",&l);
        for(i=1;i<=l;++i)
            scanf("%d",v+i);
        pos = 1;
        if(l == 1)
            printf("1\n");
        else
        {
            if(v[1] == 3 || (v[1] == 1 && v[2] == 2 && l == 3))
                printf("%d\n",c());
            else if(v[1] == 2 || (v[1] == 1 && v[3] == 3 && l >= 5))
                printf("%d\n",b());
            else
                printf("0\n");
        }
    }
    return 0;
}