#include<fstream>
#include<string>
using namespace std;
char a[10000],b1[3]="2B",b2[6]="1A3AC",c1[4]="3BC",c2[4]="12A",b[10000];
int n,m,l,i,j,nr,nrp,k;
int main()
{
	ifstream f("perle.in");
	ofstream g("perle.out");
	f>>n;
	for(i=0;i<n;i++)
	{
		f>>l;
		for(j=0;j<l;j++)
			f>>a[j];
		if(l==1)
			g<<"1"<<"\n";
		if(l==2)
			g<<"0"<<"\n";
		if(l==3 && a[0]=='1' && a[1]=='2')
			g<<"1"<<"\n";
		if(l==3 && a[0]!='1')
			g<<"0"<<"\n";
		if(l>3)
		{
			nrp=0;
			if(a[0]=='1')
			{
				strcpy(b,b2);
				while(strlen(b)<l)
				{
					for(j=0;j<strlen(b);j++)
					{
						if(b[j]=='A')
							b[j]=a[j];
						if(b[j]=='B')
						{
							if(a[j]=='2')
							{
								nr=strlen(b);
								for(k=0;k<strlen(b1);k++)
									b[k+nr-1]=b1[k];
							}
							else
							{
								nr=strlen(b);
								for(k=0;k<strlen(b2);k++)
									b[k+nr-1]=b2[k];
							}
						}
						if(b[j]=='C')
						{
							if(a[j]=='2')
								b[j]=a[j];
							if(a[j]=='3')
							{
								nr=strlen(b);
								for(k=0;k<strlen(c1);k++)
									b[k+nr-1]=c1[k];
							}
							else
								if(a[j]=='1')
								{
									nr=strlen(b);
									for(k=0;k<strlen(c2);k++)
										b[k+nr-1]=c2[k];
								}
						}
					}
				}
				g<<b<<"\n";
			}
			if(a[0]=='2')
			{
				strcpy(b,b1);
				while(strlen(b)<l)
				{
					for(j=0;j<strlen(b);j++)
					{
						if(b[j]=='A')
							b[j]=a[j];
						if(b[j]=='B')
						{
							if(a[j]=='2')
							{
								nr=strlen(b);
								for(k=0;k<strlen(b1);k++)
									b[k+nr-1]=b1[k];
							}
							if(a[j]=='1')
							{
								nr=strlen(b);
								for(k=0;k<strlen(b2);k++)
									b[k+nr-1]=b2[k];
							}
						}
						if(b[j]=='C')
						{
							if(a[j]=='2')
								b[j]=a[j];
							if(a[j]=='3')
							{
								nr=strlen(b);
								for(k=0;k<strlen(c1);k++)
									b[k+nr-1]=c1[k];
							}
							else
								if(a[j]=='1')
								{
									nr=strlen(b);
									for(k=0;k<strlen(c2);k++)
										b[k+nr-1]=c2[k];
								}
						}
					}
				}
			}
			if(a[0]=='3')
			{
				strcpy(b,c1);
				while(strlen(b)<l)
				{
					for(j=0;j<strlen(b);j++)
					{
						if(b[j]=='A')
							b[j]=a[j];
						if(b[j]=='B')
						{
							if(a[j]=='2')
							{
								nr=strlen(b);
								for(k=0;k<strlen(b1);k++)
									b[k+nr-1]=b1[k];
							}
							else
							{
								nr=strlen(b);
								for(k=0;k<strlen(b2);k++)
									b[k+nr-1]=b2[k];
							}
						}
						if(b[j]=='C')
						{
							if(a[j]=='2')
								b[j]=a[j];
							if(a[j]=='3')
							{
								nr=strlen(b);
								for(k=0;k<strlen(c1);k++)
									b[k+nr-1]=c1[k];
							}
							else
								if(a[j]=='1')
								{
									nr=strlen(b);
									for(k=0;k<strlen(c2);k++)
										b[k+nr-1]=c2[k];
								}
						}
					}
				}
			}
			for(k=0;k<l;k++)
				if(a[k]==b[k])
					nrp++;
			if(nrp==l)
				g<<"1"<<"\n";
			if(nrp!=l)
				g<<"0"<<"\n";
		}
	}
}