#include <cstdio>
#define MAX_N 10001

int A[MAX_N],L;

int fc(int);

int fb(int k)
{
    if(A[k] == 2)
        return fb(k+1);
    if(A[k] == 1 && A[k+2] == 3)
        return fc(k+4);
    return fc(k+1);
}

int fc(int k)
{
    if(A[k] == 2 )
    {
        if(k == L-1)
            return 1;
        return fc(k+1);
    }
    if(A[k] == 1 && A[k+1] == 2)
    {
        if(k+3 == L)
            return 1;
        return fc(k+3);
    }
    if(A[k] == 3)
        return fb(k+1);
    return 0;
}

void read()
{
    L = 0;
    char S[100000];
    gets(S);

    int k=0,p = 0,i=0;
    for(; S[k] != ' '; k++)
      L = L*10 + (S[k] - '0');
    for(k++; S[k] != '\n'; k++)
    {
        if(S[k] == ' ')
            A[i++] = p,p=0;
        else
            p = p*10 + (S[k] - '0');
    }

}

int solve()
{
    read();
    if(L == 1)
        return 1;
    if(L == 2)
        return 0;
    if(A[0] == 3)
        return fc(0);
    return fb(0);
}

int main()
{
    freopen("perle.in","r",stdin);
    freopen("perle.out","w",stdout);
    int nrt;
    scanf("%d\n",&nrt);
    for(int i=0; i<nrt; i++)
        printf("%d\n",solve());
}