#include <iostream>
#include <fstream>
#include <queue>

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

int n,i,j,nr,id;
char v[10010],k;
queue<char> p;
bool rez;

bool pot(char ch)
{
	id=1;
	while(!p.empty())	p.pop();
	p.push(ch);
	while(id<=n && p.size())
	{
		k=p.back();
		if(k=='A'||v[id]==k)
		{	
			id++;
			p.pop();
		}
		else if(k=='B')
		{	
			if(v[id]=='2')	id++;
			else if(v[id]=='1'&&v[id+2]=='3')
			{
				id+=4;
				p.pop();
				p.push('C');
			}
			else return 0;
		}
		else if(k=='C')
		{
			if(v[id]=='2')
			{	id++;	p.pop();	}
			else if(v[id]=='3')
			{	id++;	p.push('C');	p.push('B');	}
			else if(v[id]=='1'&&v[id+1]=='2')
			{	id+=3;	p.pop();	}
			else return 0;
		}
		else return 0;
	}
	if(p.size() || id<=n)	return 0;
	return 1;
}

int main() {
	
	/*
	 A -> 1 | 2 | 3
	 B -> 2B | 1A3AC
	 C -> 2 | 3BC | 12A
	 */
	
	fin>>nr;
	while(nr--)
	{
		fin>>n;
		for(i=1;i<=n;i++)
			fin>>v[i];
		rez=pot('A');
		rez=max(rez,pot('B'));
		rez=max(rez,pot('C'));
		fout<<rez<<"\n";
	}
}