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

using namespace std;

int n,l,i,j,v[10010],x[11010],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];
else
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;
}
else
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;
}
else
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 curatare()
{
int i;
i=1;
while (x[i]!=0)
{
x[i]=0;
i++;
}
}

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,j,0);
//fill_n(x,j,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();
}

curatare();

}


return 0;
}