#include<cstdio>
#define N 10002
char a[4][2],b[3][6],c[4][4],s1[N];
short int n,x;
void mat_c(int);
void mat_b(int);
bool ok=false;
void matrice()
{
	a[0][0]=3;
	a[1][0]=a[2][0]=a[3][0]=1;
	a[1][1]='1';
	a[1][2]='2';
	a[1][3]='3';
	b[0][0]=2;
	b[1][0]=2;b[2][0]=5;
	b[1][1]='2';b[1][2]='B';
	b[2][1]='1';b[2][2]='A';b[2][3]='3';b[2][4]='A';b[2][5]='C';
	c[0][0]=3;
	c[1][0]=1;c[1][1]='2';
	c[2][0]=3;c[2][1]='3';c[2][2]='B';c[2][3]='C';
	c[3][0]=3;c[3][1]='1';c[3][2]='2';c[3][3]='A';
	
}
void potriveste()
{
	int cx=x;
	if (s1[x]=='3')
	{
		if (x+c[2][0]-1<=n&&!ok)
		mat_c(2);
		if (!ok)
			x=cx;
	}
	else
		if (s1[x]=='2')
		{
			if (x+c[1][0]-1<=n&&!ok)
			mat_c(1);
			if (!ok)
				x=cx;
			
			if (x+b[1][0]-1<=n&&!ok)
			mat_b(1);
			if (!ok)
				x=cx;
		}
		else
			if (s1[x]=='1')
			{
				if (x+c[3][0]-1<=n&&!ok)
				mat_c(3);
				if (!ok)
				x=cx;
				
				if (x+b[2][0]-1<=n&&!ok)
				mat_b(2);
				if (!ok)
				x=cx;
				
			}
}
void mat_c(int y)
{
	int cx=x;
	for (int i=1; i<=c[y][0]; ++i)
	{
		if (s1[x]==c[y][i]||c[y][i]=='A')
		{
			++x; 
			continue;
		}
		if (c[y][i]=='B')
		{
			if (s1[x]=='2'&&x+b[1][0]-1<=n)
			{
				mat_b(1);
				if (!ok)
				{
				x=cx;
				//x1=cx1;
				}
			}
			if (s1[x]=='1'&&x+b[2][0]-1<=n)
			{
				mat_b(2);
				if (!ok)
				{
				x=cx;
				//x1=cx1;
				}
			}
			//potriveste(x);
		}
		if (c[y][i]=='C')
		{
			if (s1[x]=='2'&&x+c[1][0]-1<=n)
			{
				mat_c(1);
				if (!ok)
				{
				x=cx;
				//x1=cx1;
				}
			}
			if (s1[x]=='3'&&x+c[2][0]-1<=n)
			{
				mat_c(2);
				if (!ok){
				x=cx;
				//x1=cx1;
				}
			}
			if (s1[x]=='1'&&x+c[3][0]-1<=n)
			{
				mat_c(3);
				if (!ok)
				{
				x=cx;
				//x1=cx1;
				}
			}
		}
	}
	if (n==x-1)
		ok=true;
	else
		x=cx;
}
void mat_b( int y)
{
	int cx=x;
	for (int i=1; i<=b[y][0]&&x<=n; ++i)
	{
		if (s1[x]==b[y][i]||b[y][i]=='A')
		{
			++x; 
			continue;
		}
		if (b[y][i]=='B')
		{
			if (s1[x]=='2'&&x+b[1][0]-1<=n)
			{
				mat_b(1);
				if (!ok)
				{
				x=cx;
				//x1=cx1;
				}
			}
			if (s1[x]=='1'&&x+b[2][0]-1<=n)
			{
				mat_b(2);
				if (!ok){
				x=cx;//x1=cx1;
				}
			}
			//potriveste(x);
		}
		if (b[y][i]=='C')
		{
			if (s1[x]=='2'&&x+c[1][0]-1<=n)
			{
				mat_c(1);
				if (!ok){
				x=cx;//x1=cx1;
				}
			}
			if (s1[x]=='3'&&x+c[2][0]-1<=n)
			{
				mat_c(2);
				if (!ok){
				x=cx;//x1=cx1;
				}
			}
			if (s1[x]=='1'&&x+c[3][0]-1<=n)
			{
				mat_c(3);
				if (!ok){
				x=cx;
				//x1=cx1;
				}
			}
		}
	}
	if (n==x-1)
		ok=true;
	else
		x=cx;
}

void citire()
{
	freopen("perle.in","r",stdin);
	freopen("perle.out","w",stdout);
	short int nr;
	scanf("%hd",&nr);
	while (nr)
	{
		scanf("%hd ",&n);
		short int h=0;
		for(int i=1; i<=n; ++i)
		{
			scanf("%hd",&h);
			s1[i]=h+'0';
		}
		ok=false;
		x=1;
		potriveste();
		if (ok||n==1)
			printf("1\n");
		else
			printf("0\n");
		//printf("%s\n",s1);
		--nr;
	}
}
int main()
{
	matrice();
	citire();
	return 0;
}