#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
using namespace std;

const string file = "perle";

const string infile = file + ".in";
const string outfile = file + ".out";

const int INF = 0x3f3f3f3f;

bool readB(vector<int>& v, int& c, int size);
bool readC(vector<int>& v, int& c, int size);

bool readB(vector<int> &v, int& c, int size)
{
	if(size <= c)
		return false;

	if(v[c] == 2)
	{
		c++;
		return readB(v, c, size);
	}
	else if(c + 3 < size && v[c] == 1 && v[c+2] == 3)
	{
		c += 4;
		return readC(v, c, size);
	}
	return false;
}


bool readC(vector<int>& v, int& c, int size)
{
	if(size <= c)
		return false;

	if(v[c] == 2)
	{
		c++;
		return true;
	}
	else if(v[c] == 3)
	{
		c++;
		if (readB(v, c, size))
			return readC(v, c, size);
		else 
			return false;
	}
	else if(c + 2 < size && v[c] == 1 && v[c+1] == 2)
	{
		c += 3;
		return true;
	}
	return false;
}


int main()
{
	fstream fin(infile.c_str(), ios::in);
	fstream fout(outfile.c_str(), ios::out);

	int N;
	fin >> N;
	vector<int> sir(10000);
	for(int i = 0; i < N; i++)
	{
		int M;
		fin >> M;
		
		for(int j = 0; j < M; j++)
		{
			fin >> sir[j];
		}

		int z = 0;
		bool a = (M == 1);
		bool b = readB(sir, z, M);
		if ( z != M) b = false;
		z = 0;
		bool c = readC(sir, z, M);
		if (z != M) c = false;

		if(a || b || c)
			fout << "1\n";
		else 
			fout << "0\n";

	}

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