/* Ivan Nicolae - Bucuresti */
#include <stdio.h>
#include <string.h>

#define NMAX 10002
#define _fin "perle.in"
#define _fout "perle.out"

int i,n,A[NMAX],m;
/* A=4 B=5 C=6
   4 -> 1 | 2 | 3
   5 -> 25 | 14346
   6 -> 2 | 356 | 124 */

int B_unu(void)
{
 if (A[n-1]==2 && A[n]==5)
   return 1;
 return 0;
}

int B_doi(void)
{
 if ((A[n]==6 || A[n]==2) && (A[n-1]==1 || A[n-1]==2 || A[n-1]==3 || A[n-1]==4)
   && A[n-2]==3 && (A[n-3]==1 || A[n-3]==2 || A[n-3]==3 || A[n-3]==4) && A[n-4]==1)
   return 1;
 return 0;
}

int C_doi(void)
{
 if ((A[n]==6 || A[n]==2) && A[n-1]==5 && A[n-2]==3)
   return 1;
 return 0;
}

int C_trei(void)
{
 if ((A[n]==1 || A[n]==2 || A[n]==3 || A[n]==4) && A[n-1]==2 && A[n-2]==1)
   return 1;
 return 0;
}

void ReadData(void)
{
 int i,j;
 freopen("perle.in","r",stdin);
 freopen("perle.out","w",stdout);

 scanf("%d",&m);
 for (int step=1;step<=m;step++)
    {
     memset(A,0,sizeof(A));
     scanf("%d",&n);
     for (i=1;i<=n;i++)
        scanf("%d",&A[i]);

     while (n != 1)
          {
           int gasit=0;
           if (B_unu())
             { A[--n]=5; gasit=1;}
           if (B_doi())
             { n-=4; A[n]=5; gasit=1;}
           if (C_doi())
             { n-=2; A[n]=6; gasit=1;}
           if (C_trei())
             { n-=2; A[n]=6; gasit=1;}
           if (!gasit)
             break;
          }
     if (n==1)
       printf("1\n");
       else printf("0\n");
    }

 fclose(stdin);
 fclose(stdout);
}

int main()
{
 ReadData();
 return 0;
}