#include <cstdlib>
#include <iostream>
#include <list>

using namespace std;

bool generatedByA (list<int> perle);
bool generatedByB (list<int> perle);
bool generatedByC (list<int> perle);
list<int> removeTrailing2(list<int> perle);

bool generatedByA (list<int> perle)
{
	if (perle.size() > 1) return false;
	return true;
}

bool generatedByB (list<int> perle)
{
	if (perle.size() < 1) return false;
	perle = removeTrailing2(perle);

	if (perle.size() < 5) return false;
	if (perle.front() != 1) return false;
	perle.pop_front();
	perle.pop_front();
	if (perle.front() != 3) return false;
	perle.pop_front();
	perle.pop_front();
	return generatedByC(perle);
}

bool generatedByC(list<int> perle)
{
	if (perle.size() < 1) return false;
	if (perle.size() == 1 && perle.front() == 2) return true;
	if (perle.size() == 3 && perle.front() == 1)
	{
		perle.pop_front();
		if (perle.front() == 2) return true;
		return false;
	}
	if (perle.front() == 3)
	{
		perle.pop_front();
		if (perle.size() < 1) return false;
		if (perle.back() == 2)
		{
			perle.pop_back();
			if (generatedByB(perle)) return true; // C -> 2 case

			if (perle.size() < 2) return false; // C -> 12A case
			if (perle.back() == 2)
			{
				perle.pop_back();
				if (perle.back() == 1) 
				{
					perle.pop_back();
					return generatedByB(perle);
				}
			}
			return false;
		}
		else
		{
			perle.pop_back();
			if (perle.size() < 2) return false; // C -> 12A case
			if (perle.back() == 2)
			{
				perle.pop_back();
				if (perle.back() == 1) 
				{
					perle.pop_back();
					return generatedByB(perle);
				}
			}
			return false;
		}

	}
	return false;
}

list <int> removeTrailing2 (list<int> perle)
{
	list<int> ans = perle;
	while(ans.front() == 2) ans.pop_front();
	return ans;
}

int main()
{
	freopen("perle.in", "r", stdin);
	freopen ("perle.out", "w", stdout);

	int N, L;
	cin >> N;

	for (int i = 1; i <= N; ++i)
	{
		cin >> L;
		list<int> perle;
		for (int j = 1; j <= L; ++j)
		{
			int perla;
			cin >> perla;
			perle.push_back(perla);
		}	
		if (generatedByA(perle) || generatedByB(perle) || generatedByC(perle))
			cout << 1 << endl;
		else
			cout << 0 << endl;
	}


	return 0;
}