#include <stack>
#include <iostream>
#include <fstream>
using namespace std;

void print_st(stack<char> st){
	while(!st.empty()){
		cout << st.top();
	 	st.pop(); } }

bool verifica(ifstream& f){
	int nr_perle = 0;
	f >> nr_perle;
	char nou;
	stack<char> posibilitati[3];
	posibilitati[0].push('A');
	posibilitati[1].push('B');
	posibilitati[2].push('C');
	bool e_posibil[3] = {true, true, true};
	for(int i = 0; i < nr_perle; ++i){
		f.ignore();
		nou = f.get();
		for(int j = 0; j < 3; ++j){
			if(posibilitati[j].empty()){
				e_posibil[j] = false; }
			else if(e_posibil[j]){
				switch(posibilitati[j].top()){
				default:
					if(posibilitati[j].top() == nou){
						posibilitati[j].pop(); }
					else{
						e_posibil[j] = false; }
					break;
				case 'A':
					posibilitati[j].pop();
					break;
				case 'B':
					switch(nou){
					case '1':
						posibilitati[j].pop();
						posibilitati[j].push('C');
						posibilitati[j].push('A');
						posibilitati[j].push('3');
						posibilitati[j].push('A'); 
						break;
					case '3':
						e_posibil[j] = false;
						break; }
					break;
				case 'C':
					switch(nou){
					case '1':
						posibilitati[j].pop();
						posibilitati[j].push('A');
						posibilitati[j].push('2');
						break;
					case '2':
						posibilitati[j].pop();
						break;
					case '3':
						posibilitati[j].push('B');
						break; }
					break; } } } }
	return (e_posibil[0] && posibilitati[0].empty()) ||
		(e_posibil[1] && posibilitati[1].empty()) ||
		(e_posibil[2] && posibilitati[2].empty()); }

int main(){
	ifstream f("perle.in");
	ofstream g("perle.out");
	int n = 0;
	f >> n;
	for(int i = 0; i < n; ++i){
		g << verifica(f) << '\n'; }
	return 0; }