#include<iostream>
#include<fstream>
#include<queue>
#include<stack>

using namespace std;
int main(void)
{
	int n,nrLin,j,k,ok,i;
	char vec[10000],*p,stiva[10001];
	fstream f,g;
	f.open("perle.in",ios::in);
	g.open("perle.out",ios::out);
	f>>nrLin;
	for(i=1;i<=nrLin;i++)
	{
		f>>n;
		for (j=0;j<=n-1;j++)
			f>>vec[j];
		vec[j]='\0';
		p=vec;
		ok=1;
		k=0;//nivel siva
		if (n==1)
			p++;
		else
			if (n==3)
				if (*p='1' && *(p+1)=='2')
					p=p+3;//C->12A
				else
					ok=0;
			else 
				if (*p=='3')
					stiva[++k]='C';
				else
						stiva[++k]='B';
		while (k!=0 && ok==1 && *p!=NULL)				
		{
			if(stiva[k--]=='B')// extragere din stiva
			{
				if (*p=='2')
					{
						stiva[++k]='B';
						p++;
					}
				else
					if (*p=='1' && *(p+1)!=NULL && *(p+2)=='3' && *(p+3)!=NULL)
					{
						stiva[++k]='C';
						p=p+4;
					}
					else
						ok=0;
			}
			else
			{
				if(*p=='2')
					p++;
				else
					if(*p=='3')
					{
						stiva[++k]='C';
						stiva[++k]='B';
						p=p+1;
					}
					else
						if (*p=='1' && *(p+1)=='2' && *(p+2)!=NULL)
							p=p+3;
						else
							ok=0;
			}
		}
		if (k==0 && ok==1 && *p==NULL)
			g<<1<<'\n';
		else
			g<<0<<'\n';
	}
}