#define DM 10001
#include <fstream>
using namespace std;

ifstream fi ("perle.in");
ofstream fo ("perle.out");
int n, v[DM];
pair <int, int> a;

pair <int, int> verif(int ind, int c)//urmatoarea pozitie; ind - pozitia curenta; c - caracterul cautat
{
	if (ind > v[0])
		return {0, ind};
	pair <int, int> b;
	if (c == 1)
		return {1, ind + 1};
	if (c == 2)
	{
		if (v[ind] == 3)
			return {0, ind};
		if (v[ind] == 2)
			return verif(ind + 1, 2);
		b = verif(ind + 4, 3);
		if (b.first && v[ind] == 1 && v[ind+2] == 3)
			return {1, b.second};
		else
			return {0, ind};
	}
	if (c == 3)
	{
		if (v[ind] == 1)
		{
			b = verif(ind + 2, 1);
			if (v[ind+1] == 2)
				return b;
			else
				return {0, ind};
		}
		if (v[ind] == 2)
			return {1, ind + 1};
		if (v[ind] == 3)
		{
			b = verif(ind + 1, 2);
			if (b.first)
				b = verif(b.second, 3);
			return b;
		}
	}
}

int main()
{
	fi >> n;
	while (n--)
	{
		fi >> v[0];
		for (int i = 1; i <= v[0]; ++i)
			fi >> v[i];
		if (v[0] == 1)
			fo << 1 << '\n';
		else if (v[1] == 1)
		{
			if (v[0] == 3 && v[2] == 2)
				fo << 1 << '\n';
			a = verif(5, 3);
			fo << (v[3] == 3 && a.second == v[0] + 1 && a.first) << '\n';
		}
		else if (v[1] == 2)
		{
			a = verif(2, 2);
			fo << (a.first && a.second == v[0] + 1) << '\n';
		}
		else
		{
			a = verif(2, 2);
			if (a.first)
				a = verif(a.second, 3);
			fo << (a.first && a.second == v[0] + 1) << '\n';
		}
	}
	return 0;
}