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

int i,T,N,ok,len;
int v[10001];
char sir[10101],aux[10101];

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

	scanf("%d",&T);

	for(;T>0;T--)
	{
		scanf("%d",&N);

		for(i=0;i<N;i++) scanf("%d",&v[i]);

		if(N==1) printf("1\n");
		else
		if(N==2) printf("0\n");
		else
		if(N==3)
		{
			if(v[0]!=1) printf("0\n");
			else
			if(v[1]!=2) printf("0\n");
			else
			printf("1\n");
		}
		else
		{
			memset(sir,'\0',sizeof(sir));

			if(v[0]==1) strcpy(sir,"1A3AC");
			else
			if(v[0]==2) strcpy(sir,"2B");
			else
			if(v[0]==3) strcpy(sir,"3BC");

			ok=1;

			for(i=1;i<N;i++)
			{
				if(v[i]==1)
				{
					if(sir[i]=='A') sir[i]='1';
					else
					if(sir[i]=='B')
					{
						memset(aux,'\0',sizeof(aux));
						strcpy(aux,sir+i+1);
						strcpy(sir+i,"1A3AC");
						strcpy(sir+i+5,aux);
					}
					else
					if(sir[i]=='C')
					{
						memset(aux,'\0',sizeof(aux));
						strcpy(aux,sir+i+1);
						strcpy(sir+i,"12A");
						strcpy(sir+i+3,aux);
					}
					else
					if(sir[i]!='1')
					{
						ok=0;
						break;
					}
				}
				else
				if(v[i]==2)
				{
					if(sir[i]=='A') sir[i]='2';
					else
					if(sir[i]=='B')
					{
						memset(aux,'\0',sizeof(aux));
						strcpy(aux,sir+i+1);
						strcpy(sir+i,"2B");
						strcpy(sir+i+2,aux);
					}
					else
					if(sir[i]=='C') sir[i]='2';
					else
					if(sir[i]!='2')
					{
						ok=0;
						break;
					}
				}
				else
				if(v[i]==3)
				{
					if(sir[i]=='A') sir[i]='3';
					else
					if(sir[i]=='C')
					{
						memset(aux,'\0',sizeof(aux));
						strcpy(aux,sir+i+1);
						strcpy(sir+i,"3BC");
						strcpy(sir+i+3,aux);
					}
					else
					if(sir[i]!='3')
					{
						ok=0;
						break;
					}
				}
				len=strlen(sir)-1;
				if(len>N)
				{
					ok=0;
					break;
				}
			}

			if(ok) printf("1\n");
			else printf("0\n");
		}
	}

	return 0;
}