#include<iostream>
#include<fstream.h>
#include<string.h>

using namespace std;

ifstream fin("perle.in");
ofstream fout("perle.out");

int t,lungime,i,j,rez;
char s[12000],v[11000];

int solve(int k,char c)
{	
	int l=0;
	
	if(k>lungime)
		if(strcmp(s,v)==0)
			return 1;
		else
			return 0;
		
	if(c=='A')
	{
		if(v[k]==1)
		{
			s[k]=1;
			k++;
		}
		else
			if(v[k]==2)
			{
				s[k]=2;
				k++;
			}
		else
			if(v[k]==3)
			{
				s[k]=3;
				k++;
			}

	}
	if(c=='B')
	{
		if(v[k]==2)
		{
			s[k]=2;
			s[k+1]='B';
			return solve(k+1,'B');
		}
		else
			if(v[k]==1)
			{
				s[k]=1;
				s[k+1]='A';
				s[k+2]=3;
				s[k+3]='A';
				s[k+4]='C';
				return solve(k+1,'A');
			}
	}
	if(c=='C')
	{
		if(v[k]==2)
		{
			s[k]=2;
			k++;
		}
		else
			if(v[k]==3)
			{
				s[k]=3;
				s[k+1]='B';
				s[k+2]='C';
				return solve(k+1,'B');
			}
		else
			if(v[k]==1)
			{
				s[k]=1;
				s[k+1]=2;
				s[k+2]='A';
				return solve(k+2,'A');
			}
	}
	
	int ok=1;
	for(l=k;l<lungime;l++)
		{
			if(s[l]=='A')
			{
				ok=0;
				return solve(l,'A');
			}
			else
				if(s[l]=='B')
				{
					ok=0;
					return solve(l,'B');
				}
			else
				if(s[l]=='C')
				{
					ok=0;
					return solve(l,'C');
				}
		}
		
	
	if(k>=lungime)
		if(strcmp(s,v)==0)
			return 1;
		else
			return 0;
	
}
	
	
	


int main()
{
	fin>>t;
	for(i=0;i<t;i++)
	{
		fin>>lungime;
		for(j=0;j<lungime;j++)
		{
			fin>>v[j];
			v[j]=v[j]-48;
		}
		rez = solve(0,'A');
		for(j=0;j<lungime;j++)
			s[j]=0;
		if(rez !=1)
			rez=solve(0,'B');
		for(j=0;j<lungime;j++)
			s[j]=0;
		if(rez !=1)
			rez=solve(0,'C');
		for(j=0;j<lungime;j++)
			s[j]=0;
		fout<<rez<<'\n';
		for(j=0;j<lungime;j++)
			v[i]=0;
	}
	
	return 0;
}