#include <iostream>
#include <fstream>
using namespace std;
ifstream in("perle.in");
ofstream out("perle.out");
int sir[10001],n,k,adevar;
void c();
void a()
{
	if (k > n){ adevar = false; return; }
	k++;
}
void b()
{
	if (k > n){ adevar = false; return; }
	if (sir[k] == 2)
	{
		k++;
		b();
	}
	else
	{
		if (n - k >= 4)
		{
			if (sir[k] == 1 && sir[k + 2] == 3)
			{
				k += 4;
				c();
			}
			else
			{
				adevar = false;
				return;
			}
		}
		else
		{
			adevar = false;
			return;
		}
	}

}
void c()
{
	if (k > n){ adevar = false; return; }
	if (sir[k] == 1)
	{
		if (n - k >= 2)
		{
			if (sir[k] == 1 && sir[k + 1] == 2)
			{
				k+=3;
			}
			else
			{
				adevar = false;
			}
		}
		else
		{
			adevar = false;
			return;
		}
	}
	else if (sir[k] == 2)
	{
		k++;
	}
	else if (sir[k] == 3)
	{
		k++;
		b();
		c();
	}
}
void rez()
{
	int i;
	in >> n;
	k = 1;
	adevar = true;
	for (i = 1; i <= n; i++)
	{
		in >> sir[i];
	}
	if (n == 1)
	{
		out << "1";
		return;
	}
	if (n == 3)
	{
		if (sir[1] == 1 && sir[2] == 2)
		{
			out << "1";
		}
		else
		{
			out << "0";
		}
		return;
	}
	if (sir[1] == 3)
	{
		c();
	}
	else
	{
		b();
	}
	if (k != n + 1)
	{
		adevar = false;
	}
	out << adevar;
}
int main()
{
	int i, t;
	in >> t;
	for (i = 1; i <= t; i++)
	{
		rez();
		out << "\n";
	}
}