#include <fstream>
#include <string>
using std::string;

std::ifstream in("perle.in");
std::ofstream out("perle.out");

string patternA[] = { "1", "2", "3" };
string patternB[] = { "2B", "1A3AC" };
string patternC[] = { "2", "3BC", "12A" };

string input;
int n;

bool process(string toProcess, string pattern) {
	int letterIndex = -1;

	if (pattern.length() == 0 && toProcess.length() > 0) return false;

	for (int i = 0; i < toProcess.length(); i++) {
		if ('A' <= toProcess[i] && toProcess[i] <= 'C') {
			letterIndex = i;
			break;
		}
		else if (pattern.length() < i || toProcess[i] != pattern[i]) return false;
	}

	if (letterIndex == -1) {
		if (toProcess.length() != pattern.length()) return false;
		return true;
	}

	toProcess = toProcess.erase(0, letterIndex);
	pattern = pattern.erase(0, letterIndex);
	bool result;
	switch (toProcess[0]) {
	case 'A':
		result = process(patternA[0] + ((toProcess.length() > 0) ? toProcess.substr(1) : ""), pattern);
		if (!result) result = process(patternA[1] + ((toProcess.length() > 0) ? toProcess.substr(1) : ""), pattern);
		if (!result) result = process(patternA[2] + ((toProcess.length() > 0) ? toProcess.substr(1) : ""), pattern);
		return result;
		break;
	case 'B':
		result = process(patternB[0] + ((toProcess.length() > 0) ? toProcess.substr(1) : ""), pattern);
		if (!result) result = process(patternB[1] + ((toProcess.length() > 0) ? toProcess.substr(1) : ""), pattern);
		return result;
		break;
	case 'C':
		result = process(patternC[0] + ((toProcess.length() > 0) ? toProcess.substr(1) : ""), pattern);
		if (!result) result = process(patternC[1] + ((toProcess.length() > 0) ? toProcess.substr(1) : ""), pattern);
		if (!result) result = process(patternC[2] + ((toProcess.length() > 0) ? toProcess.substr(1) : ""), pattern);
		return result;
		break;
	default:
		exit(EXIT_FAILURE);
	}
}

int main() {
	in >> n;

	for (int i = 0; i < n; i++) {
		input = "";
		int temp;
		in >> temp;
		
		for (int j = 0; j < temp; j++) {
			int temp;
			in >> temp;
			input.push_back(temp + '0');
		}

		bool result = process("A", input);
		if (!result) result = process("B", input);
		if (!result) result = process("C", input);

		if (result) {
			out << 1 << '\n';
		}
		else {
			out << 0 << '\n';
		}
	}
}