#include <cstdio>
#include <cstring>

using namespace std;

int n, lu[5], l;
int a[10005];
char perle[5][5][8];
char sol[10005];
int da;
void tranB(int &poz);
void tranC(int &poz);

/**int pot(int lit)
{
    int lun=strlen(sol);
    if(sol[0]>=lu[0])
    {
        if(strcmp(sol, a)==0)
        {
            da=1;
            return 1;
        }
        return 0;
    }
    for(int v=1;v<=lun;v++)
    {
        if()
    }
}**/


void tranC(int &poz)
{
    if(a[poz]==2)
        return;
    if(a[poz]==3)
    {
        poz++;
        tranB(poz);
        poz++;
        tranC(poz);
    }
    if(a[poz]==1 && a[poz+1]==2)
    {
        poz+=2;
        return;
    }
}

void tranB(int &poz)
{
    if(poz>l)
        return;
    if(a[poz]==1 && a[poz+2]==3)
    {
        poz+=4;
        tranC(poz);
    }
    if(a[poz]==2)
    {
        poz++;
        tranB(poz);
    }
}

int main()
{
    freopen("perle.in", "r", stdin);
    freopen("perle.out", "w", stdout);
    scanf("%d\n", &n);
    /**strcpy(perle[1][1], "1");
    strcpy(perle[1][2], "1A3AC");
    strcpy(perle[1][3], "12A");
    strcpy(perle[2][1], "2");
    strcpy(perle[2][2], "2B");
    strcpy(perle[2][3], "2");
    strcpy(perle[3][1], "3");
    strcpy(perle[3][2], "3BC");
    lu[1]=3;
    lu[2]=2;
    lu[3]=3;**/
    for(int e=0;e<n;e++)
    {
        scanf("%d ", &l);
        for(int i=1;i<=l;i++)
            scanf("%d ", &a[i]);
        scanf("\n");
        int ok=0;
        if(l>1)
        {
            int poz=1;
            if(a[poz]==2 || a[poz]==1)
            {
                poz++;
                tranB(poz);
            }
            if(poz==l)
                printf("1\n");
            else
            {
                //poz++;
                tranC(poz);
                if(poz==l)
                    printf("1\n");
                else
                    printf("0\n");
            }
        }
        else printf("1\n");
    }

    return 0;
}