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

using namespace std;

int n;
short stg;
int pzc;
int m;
string cifre(10002u, 0 );
string posib(10002u, 0 );
int nloc[3] = { 3, 2, 3 };
string inloc[3][3] = { { "1", "2", "3"   },
		     { "2B", "1A3AC" 	 },
		     { "2", "3BC", "12A" } };

int i,j,k;

void solv()
{
	int offset=0;
	pzc = 0;
	stg = 1;
	while ( pzc < m && stg )
	{
		if ( posib[pzc+offset] != cifre[pzc] && 
		   ( posib[pzc+offset] != 'A' && posib[pzc+offset] !='B' && posib[pzc+offset] != 'C' ) )
			stg = 0;
		else
		{
			stg = 1;
			if ( posib[pzc+offset] == 'A' || posib[pzc+offset] == 'B' || posib[pzc+offset] == 'C' )
			{
				for ( i = 0; i < nloc[ posib[pzc+offset] - 'A' ] ; i++ )
				{
					if ( inloc[ posib[pzc+offset] - 'A' ][i][0] == cifre[pzc] )
					{
						posib.insert( pzc+offset+1, inloc[posib[pzc+offset] - 'A' ][i] );
						posib[pzc+offset] = ' ';
						offset +=1;
						stg = 1;
						break;
					}
				}
			}
		}
		pzc+=1;
	}
}
		

int main()
{
	freopen("perle.in","r",stdin);
	freopen("perle.out","w",stdout);
	
	scanf("%d\n", &n);
	
	while (n)
	{
		n--;
		scanf("%d ", &m);
		for ( i = 0; i < m; i++ )
			scanf("%c ", &cifre[i] );
		if ( m == 1 ) printf("1\n");
		else
		{
			// CU B
			posib.clear();
			posib = 'B';
			solv();
			for ( i = 0, j=0 ; i < m ; i++, j++ )
			{
				while ( posib[j] == ' ' ) j++;
				if ( posib[j] != cifre[i] ) { stg = 0; break; }
			}
			if ( posib[j] != 0 ) stg = 0;
			if ( !stg )
			{
				// CU C
				posib.clear();
				posib = 'C';
				solv();
			}
			printf("%d\n", stg);
		}
	}
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}