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

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

enum type { A, B, C };

#define LMAX 10005
char buf[LMAX];

bool solve_a(char *s, int len, int& idx);
bool solve_b(char *s, int len, int& idx);
bool solve_c(char *s, int len, int& idx);

bool solve_a(char *s, int len, int& idx) {
	if (idx++ >= len)
		return false;
	return true;
}

bool solve_b(char *s, int len, int& idx) {
	if (idx >= len)
		return false;

	while (idx < len && s[idx] == '2')
		++idx;

	if (idx >= len)
		return false;
	
	if (s[idx] != '1' || s[idx + 2] != '3')
		return false;

	idx += 4;
	return solve_c(s, len, idx);
}

bool solve_c(char *s, int len, int& idx) {
	if (idx >= len)
		return false;

	if (s[idx] == '2') {
		++idx;
		return true;
	}

	if (s[idx] == '1') {
		idx += 3;
		if (s[idx - 2] == '2')
			return true;
		return false;
	}

	return solve_b(s, len, idx) && solve_c(s, len, idx);
}

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

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

	if (l == 1) {
		cout << "1\n";
		return;
	}

	buf[l] = '\0';

	int idx1 = 0, idx2 = 0;
	if ((solve_b(buf, l, idx1) && idx1 == l) || (solve_c(buf, l, idx2) && idx2 == l))
		cout << "1\n";
	else
		cout << "0\n";
}

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

	while (n--)
	solve();
}