#include <fstream.h>
#include <string.h>
#include <iostream.h>
char y[10010]; int leny;
void inserez2b(int k)
{
	int j;
	for(j=leny;j>=k;j--)
		y[j+1]=y[j];
	y[k]='2';
	y[k+1]='b';
}
void inserez1a3ac(int k)
{
	int j;
	for(j=leny;j>=k;j--)
		y[j+4]=y[j];
	y[k]='1'; y[k+1]='a'; y[k+2]='3'; y[k+3]='a'; y[k+4]='c';
}
void inserez12a(int k)
{
	int j;
	for(j=leny;j>=k;j--)
		y[j+2]=y[j];
	y[k]='1'; y[k+1]='2'; y[k+2]='a';
}
void inserez3bc(int k)
{
	int j;
	for(j=leny;j>=k;j--)
		y[j+2]=y[j];
	y[k]='3'; y[k+1]='b'; y[k+2]='c';
}
int main()
{
	char x[10010];
	int i,j,n,len,change;
	fstream f("perle.in",ios::in), g("perle.out",ios::out);
	f>>n;
	for(i=1;i<=n;i++)
	{
		f>>len;
		for(j=1;j<=len;j++)
			f>>x[j];
		if(len==1)
			y[1]='a';
		else
		if(len==3&&x[1]=='1'&&x[2]=='2')
			y[1]='c';
		else
		if(x[1]=='3')
			y[1]='c';
		else
			y[1]='b';
		leny=1;
		change=0;
		for(j=1;j<=leny;j++)
			if(y[j]=='a')
				{ y[j]=x[j]; change=1; }
			else
			if(y[j]=='b')
				{
				if(x[j]=='2')
				  { inserez2b(j); change=1; leny++;}
				if(x[j]=='1')
				  { inserez1a3ac(j); change=1; leny+=4;}
				}
			else
			if(y[j]=='c')
				{
				if(x[j]=='1')
				  { inserez12a(j); change=1; leny+=2;}
				if(x[j]=='2')
				  { y[j]='2'; change=1; }
				if(x[j]=='3')
				  { inserez3bc(j); change=1; leny+=2;}
				}
		int ok=1;
		for(j=1;j<=len;j++)
			if(x[j]!=y[j])
			{	g<<0<<'\n';
				ok=0;
				break;
			}
		if(ok==1&&leny==len)
			g<<1<<'\n';
		if(ok==1&&leny!=len)
			g<<0<<'\n';



	}
	f.close(); g.close();
return 0;
}