#include <iostream>
using namespace std;
#include <fstream>
#include <string>
#include <list>

int is_sequence_good(int L, char* seq)
{	
	if (L == 1) return 1;
	if (L == 3 && seq[0] == '1' && seq[1] == '2') return 1;
	//otherwise

	list<char> expanded;
	switch (seq[0])
	{
	case '1':
		expanded.push_front('C');
		expanded.push_front('A');
		expanded.push_front('3');
		expanded.push_front('A');
		//expanded.push_front('1');
		break;
	case '2':
		expanded.push_front('B');
		//expanded.push_front('2');					
		break;
	case 3:
		expanded.push_front('C');
		expanded.push_front('B');
		//expanded.push_front('3');		
		break;
	}
	
	int pos = 1;
	while (pos < L)
	{
		//check the expanded list and the current digit; perform new expansions
		
		if (expanded.empty()) return 0;

		char x = expanded.front();
		expanded.pop_front();
		
		switch (x)
		{		
		case 'A':
			break;
		case 'B':
			switch (seq[pos])
			{
				case '1':
					expanded.push_front('C');
					expanded.push_front('A');
					expanded.push_front('3');
					expanded.push_front('A');
					//expanded.push_front('1');
					break;

				case '2':
					expanded.push_front('B');
					//expanded.push_front('2');
					break;
				case '3':
					return 0;
					break;//not reachable
			}

			break;
		case 'C':
			switch (seq[pos])
			{
			case '1':
				expanded.push_front('A');
				expanded.push_front('2');
				//expanded.push_front('1');
			case '2':
				break;
			case '3':
				expanded.push_front('C');
				expanded.push_front('B');
				//expanded.push_front('3');		
				break;
			}

			break;
		default://if (x == '1' || x == '2' || x == '3') 
			if (seq[pos] != x) return 0; 

		}		
		
		pos++;
	}

	//the size of the list is zero if the sequence is good
	if ( !expanded.empty() ) return 0;
	return 1;
}

//int pb_022_perle()
int main()
{
	int N;
	
	string in_file = "perle.in";
	string out_file = "perle.out";

	ifstream ifs;
	ifs.open(in_file.c_str());
	
	ofstream ofs;
	ofs.open(out_file.c_str());

	ifs>>N;


	//read each sequence and process it
	for (int i = 0; i < N; i++)
	{
		//the length of the i'th sequence
		int L; ifs>>L;

		//allocate storage for the sequence
		char* seq = new char[L];		
		//populate the sequence
		for (int j = 0; j < L; j++) ifs>>seq[j];

		//process the sequence
		int is_good = is_sequence_good(L, seq);
		
		//write the result to the output file
		ofs<<is_good;
		if (i < N-1) ofs<<endl;

		//release the memory
		delete[] seq;		
	}

	ifs.close();
	ofs.close();

	return 0;
}