// Include
#include <fstream>
using namespace std;

// Constante
const int sz = 10001;

// Functii
int B(int);
int C(int);

// Variabile
ifstream in("perle.in");
ofstream out("perle.out");

int tests, num;
int elements[sz];

// Main
int main()
{
	in >> tests;
	while(tests--)
	{
		in >> num;
		for(int i=1 ; i<=num ; ++i)
			in >> elements[i];
		
		if(num == 1)
		{
			out << 1 << '\n';
			continue;
		}
		
		out << ((B(1)==num+1 || C(1)==num+1)? 1 : 0) << '\n';
	}
	
	in.close();
	out.close();
	return 0;
}

int B(int pos)
{
	if(num < pos)
		return -1;
	if(elements[pos] == 2)
		return B(pos+1);
	if(elements[pos] == 1 && elements[pos+2] == 3)
		return C(pos+4);
	return -1;
}

int C(int pos)
{
	if(num < pos)
		return -1;
	if(elements[pos] == 2)
		return pos+1;
	if(elements[pos] == 1 && elements[pos+1] == 2)
		return pos+3;
	if(elements[pos] == 3)
		return C(B(pos+1));
	return -1;
}