// Perle - Infoarena

#include <cstdio>
#define Nmax 10001

int a[Nmax],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());
}