#include<cstdio>

const int N = (1<<15);

int nrc;

bool a(char*,int);
bool b(char*,int);
bool c(char*,int);

bool a(char *s,int n)
{
	if(n==1 && nrc==0)
		return true;
	if(n!=1 && nrc)
	{
		--nrc;
		return c(s+2,n-1);
	}
	return false;
}

bool b(char *s,int n)
{
	if(n==1)
		return false;
	if(s[0]=='2')
		return b(s+2,n-1);
	if(s[0]=='1' && s[4]=='3' && n>=5)
		return c(s+8,n-4);
	return false;
}

bool c(char *s,int n)
{
	if(n>2 && s[0]=='1' && s[2]=='2')
		return a(s+4,n-2);
	if(n==1 && s[0]=='2' && nrc==0)
		return true;
	if(s[0]=='2' && nrc)
		return a(s,n);
	if(s[0]=='3' && n>=7)
	{
		++nrc;
		b(s+2,n-1);
	}
	return false;
}

int main()
{
	freopen("perle.in","r",stdin);
	freopen("perle.out","w",stdout);
	int t,n;
	char s[N];
	scanf("%d\n",&t);
	while(t--)
	{
		scanf("%d ",&n);
		fgets(s,N,stdin);
		nrc=0;
		printf("%d\n",(int)(a(s,n)||b(s,n)||c(s,n)));
	}
	return 0;
}