#include <bits/stdc++.h>
using namespace std;

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

enum type {
	A, B, C
};

unordered_map<string, bool> dp[3];

bool rec(type t, const string& s) {
	auto it = dp[t].find(s);
	if (it != dp[t].end())
		return it->second;

	if (t == A)
		return (s.size() == 1);

	if (t == B)
		return dp[t][s] = ((s.size() >= 2 && s[0] == '2' && rec(B, s.substr(1))) ||
						   (s.size() >= 5 && s[0] == '1' && s[2] == '3' && rec(C, s.substr(4))));

	if (s[0] == '1')
		return dp[t][s] = (s.size() == 3 && s[1] == '2');
	if (s[1] == '2')
		return (s.size() == 1);

	for (uint i = 2; i < s.size(); ++i)
		if (rec(B, s.substr(1, i - 1)) && rec(C, s.substr(i)))
			return dp[t][s] = true;
	
	return dp[t][s] = false;
}

void solve() {
	int l;
	fin >> l;

	string s;
	s.resize(l);

	for (int i = 0; i < l; ++i)
		fin >> s[i];

	fout << (rec(A, s) || rec(B, s) || rec(C, s)) << '\n';
}

int main() {
	int n;
	fin >> n;

	while (n--)
		solve();
}