#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

int n,l,i,j,v[20010],x[20010],ll,ok,mer,k;

int fa()
{
    i=1;mer=1;j=1;
    while (i<=ll and mer==1)
    {

        if (x[i]==4)
            x[i]=v[i];
        if (x[i]==5)
            {
                if (v[i]==2)
                {
                    j++;
                    for (k=j;k>i+1;k--)
                    x[k]=x[k-1];
                    x[i]=2;x[i+1]=5;
                }
                else
                if (v[i]==1 and v[i+2]==3)
                {
                    j+=4;
                    for (k=j;k>i+4;k--)
                    x[k]=x[k-4];
                    x[i]=1;x[i+1]=4;x[i+2]=3;x[i+3]=4;x[i+4]=6;
                }
                else
                mer=0;
            }
        if (x[i]==6)
        {
            if (v[i]==2)
            x[i]=2;
            else
            if (v[i]==3)
            {
                j+=2;
                for (k=j;k>i+2;k--)
                    x[k]=x[k-2];
                x[i]=3;x[i+1]=5;x[i+2]=6;
            }
            else
            if (v[i]==1 and v[i+1]==2)
            {
                j+=2;
                for (k=j;k>i+2;k--)
                    x[k]=x[k-2];
                x[i]=1;x[i+1]=2;x[i+2]=4;
            }
            else mer=0;
        }
       if (x[i]!=v[i]) mer=0;
       if (x[ll+1]!=0) mer=0;
       i++;
       j++;

    }

    //for (i=1;i<=10;i++)
   // printf ("%d",x[i]);

    printf("%d\n",mer);

}

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

    scanf("%d",&n);

    for (l=1;l<=n;l++)
    {
        ok=1;
        fill_n(v,10009,0);
        fill_n(x,10009,0);
        scanf("%d",&ll);
        for (i=1;i<=ll;i++)
        scanf("%d",&v[i]);
        if (v[1]==1)
        {
            if (ll==1 )
            {
                printf("1\n");
                ok=0;
            }
            if(v[3]==3) x[1]=5;
            if (v[2]==2 and ll==3) x[1]=6;
        }
        if (v[1]==2)
        {
            if (ll==1)
            {
                printf("1\n"); ok=0;
            }
            if(v[2]==3)
            {
                printf("0\n");ok=0;
            }
            if (v[2]==1 or v[2]==2) x[1]=5;

        }
        if (v[1]==3)
        {
            if (ll==1)
            {
                printf("1\n"); ok=0;
            }
            if (v[2]==1 or v[2]==2) x[1]=6;
            if(v[2]==3)
            {
                printf("0\n");ok=0;
            }
        }

        if (ok==1)
        {
            //printf("\n%d\n",x[1]);
            fa();
        }



    }


    return 0;
}