#include <fstream>
#include <vector>
#include <stack>

using namespace std;

ifstream cin("perle.in");
ofstream cout("perle.out");

bool expandA(char c, stack<char>& stk) {
	stk.pop();
	return true;
}

bool expandB(char c, stack<char>& stk) {
	stk.pop();
	if (c == '1') {
		for (auto x : {'C', 'A', '3', 'A'}) {
			stk.push(x);
		}
		return true;
	} else if (c == '2') {
		stk.push('B');
		return true;
	} else {
		return false;
	}
}

bool expandC(char c, stack<char>& stk) {
	stk.pop();
	if (c == '1') {
		stk.push('A');
		stk.push('2');
		return true;
	} else if (c == '2') {
		return true;
	} else {
		stk.push('C');
		stk.push('B');
		return true;
	}
}

bool update(char c, stack<char>& stk) {
	char x = stk.top();
	stk.pop();
	return (c == x);
}

bool parse(char start, string s) {
	stack<char> stk;
	stk.push(start);

	for (auto c : s) {
		if (stk.empty()) {
			return false;
		}

		if (stk.top() == 'A') {
			if (!expandA(c, stk)) {
				return false;
			}
		} else if (stk.top() == 'B') {
			if (!expandB(c, stk)) {
				return false;
			}
		} else if (stk.top() == 'C') {
			if (!expandC(c, stk)) {
				return false;
			}
		} else {
			if (!update(c, stk)) {
				return false;
			}
		}
	}

	return stk.empty();
}

void Solve() {
	int n; cin >> n;
	string s(n, '.');
	for (int i = 0; i < n; i++) {
		cin >> s[i];
	}

	for (auto start : {'A', 'B', 'C'}) {
		if (parse(start, s)) {
			cout << "1\n";
			return;
		}
	}

	cout << "0\n";
}

int main() {
	int t; cin >> t;
	for (int i = 0; i < t; i++) {
		Solve();
	}
	return 0;
}