#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;

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

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();
			stg = ( stg && ( posib[m] == 0 ) );
			if ( !stg )
			{
				// CU C
				posib.clear();
				posib = 'C';
				solv();
			}
			printf("%d\n", stg);
		}
	}
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}