#include <fstream.h>

int L, i, Cs;
short v[10000];

short perlaB ()
{
	while (v[i] == 2)
	{
		if (L == 1) return 0;
		i++;
		L--;
	}
	if (v[i] == 3) return 0;
	if ((L >= 5) && (v[i+2] == 3))
	{
		i += 4;
		L -= 4;
		Cs++;
	}
	else return 0;
	return 1;
}

short perlaC ()
{
	if (v[i] == 2)
	{
		if (L == 1)
		{
			if (Cs == 1) return 1;
			return 0;
		}
		else
		{
			if (Cs == 0) return 0;
			else
			{
				Cs--;
				i++;
				L--;
				if (Cs == 0) return 0;
				else return perlaC ();
			}
		}
	}
	if (v[i] == 1)
	{
		if (v[i+1] == 2)
		{
			if (L == 3)
			{
				if (Cs == 1) return 1;
				return 0;
			}
			else
			{
				if (Cs == 0) return 0;
				else
				{
					Cs--;
					i += 3;
					L -= 3;
					if (Cs == 0) return 0;
					else return perlaC ();
				}
			}
		}
		else return 0;
	}
	i++;
	L--;
	Cs--;
	if (perlaB ()) Cs++;
	else return 0;
	if (Cs) return perlaC ();
	return 1;
}


short treaba ()
{
	if (L == 1) return 1;
	if (v[i] == 2)
	{
		if (perlaB ())
		{
			return perlaC ();
		}
		return 0;
	}
	if (v[i] == 1)
	{
		if (L == 3)
		{
			if (v[i+1] == 2) return 1;
			return 0;
		}
		if (perlaB ())
		{
			return perlaC ();
		}
		return 0;
	}
	i++;
	L--;
	Cs++;
	if (perlaB ()) return perlaC ();
	return 0;
}

int main ()
{
	int N, j;
	ifstream fin ("perle.in");
	ofstream fout ("perle.out");
	fin >> N;
	for (j = 0; j < N; j++)
	{
		fin >> L;
		memset (v, 0, sizeof (v));
		for (i = 0; i < L; i++)
		{
			fin >> v[i];
		}
		i = 0;
		Cs = 0;
		fout << treaba () << "\n";
	}

	fin.close ();
	fout.close ();
	return 0;
}