#include <cstdio>
#include <cstring>

using namespace std;

int n, nrel;
int sir[10005];
char perle[5][5][8];
char sol[10005];

void init()
{
    //    strcpy(perle[1][1],"1");
//    strcpy(perle[1][2],"2");
//    strcpy(perle[1][3],"3");
//    strcpy(perle[2][1],"1A3AC");
//    strcpy(perle[2][2],"2B");
//    strcpy(perle[3][1],"12A");
//    strcpy(perle[3][2],"2");
//    strcpy(perle[3][3],"3BC");

//    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],"");
//    strcpy(perle[3][3],"3BC");
}

void transB(int &poz);
void transC(int &poz);

void transB(int &poz)
{
    if(poz>nrel)
        return;
    if(sir[poz] == 1 && sir[poz+2] == 3)
    {
        poz+=4;
        transC(poz);
        return;

    }
    if(sir[poz] == 2)
    {
        poz++;
        transB(poz);
        return;
    }
    poz--;
}

void transC(int &poz)
{
    //if(poz>=nrel)
    if(poz>nrel)
        return;
    if(sir[poz] == 2)
        return;
    if(sir[poz] == 3)
    {
        poz++;
        transB(poz);
        poz++;
        transC(poz);
        return;
    }
    if(sir[poz] == 1 && sir[poz+1] == 2)
    {
        poz+=2;
        return;
    }
    poz--;
}


int main()
{

    freopen("perle.in", "r", stdin);
    freopen("perle.out", "w", stdout);

    scanf("%d", &n);



    for(int locatieSir=1; locatieSir<=n; locatieSir++)
    {
        scanf("%d", &nrel);
        for(int i=1; i<=nrel; i++)
        {
            scanf("%d", &sir[i]);
        }
        if(nrel>1)
        {
            int poz=1;
            if(sir[poz] == 2 || sir[poz] == 1)
            {
                //poz++;
                transB(poz);
            }
            if(poz == nrel)
                printf("1\n");
            else
            {
               // poz++;
                transC(poz);
                if(poz == nrel)
                    printf("1\n");
                else
                    printf("0\n");
            }
        }
        else
            printf("1\n");
    }

    return 0;
}