#include <fstream>

int A[10002];

int matchB(int, int);
int matchC(int, int);

int main(int argc, char *argv[])
{
	std::ifstream in("perle.in");
	std::ofstream out("perle.out");
	int t, n;
	in >> t;
	while (t--) {
		in >> n;
		if (n == 1) {
			out << 1 << std::endl;
			in >> n;
		} else {
			for (int i = 1; i <= n; ++i)
				in >> A[i];
			out << (matchB(1, n) == n || matchC(1, n) == n) << std::endl;
		}
	}
	in.close();
	out.close();
	return 0;
}

int matchB(int a, int nn)
{
	if (a >= nn)
		return nn + 1;
	if (A[a] == 2)
		return matchB(a + 1, nn);
	if (nn - a + 1 >= 5 && A[a] == 1 && A[a + 2] == 3)
		return matchC(a + 4, nn);
	return nn + 1;
}

int matchC(int a, int n)
{
	if (a > n)
		return n + 1;
	if (A[a] == 2)
		return a;
	int len = n - a + 1;
	if (len >= 3 && A[a] == 1 && A[a + 1] == 2)
		return a + 2;
	if (len >= 7 && A[a] == 3)
		return matchC(matchB(a + 1, n) + 1, n);
	return n + 1;
}