//https://www.infoarena.ro/problema/perle

//#pragma GCC optimize("O3")   
//#pragma GCC optimize("Ofast") 
//#pragma GCC optimize("fast-math") 
//#pragma GCC optimize("unroll-loops") 
//#pragma GCC optimize("inline")  
//#define _USE_MATH_DEFINES
//#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <fstream>
//#include <vector>
//#include <cstring>
//#include <cmath>
//#include <bitset>
#include <queue>
//#include <stack>
//#include <utility>
//#include <algorithm>
//#include <string>
//#include <map>
//#include <unordered_map>
//#include <set>
//#include <unordered_set>
//#include <cstdint>
//#include <climits>
//#include <iomanip>
//#include <cstdio>
//#include <tuple>

using namespace std;

ifstream fin("perle.in");
ofstream fout("perle.out");

string v;
int st, dr;

bool verifA(); // A
bool verifB(); // B
bool verifC(); // C

bool verifA() // A (nu cred ca am nevoie da il las)
{
	return (st < dr && (v[st] == '1' || v[st] == '2' || v[st] == '3'));
}

bool verifB() // C
{
	if (st >= dr)
		return false;

	if (dr - st >= 2 && v[st] == '2') // are mai mult de 2 elemente -> 2B
	{
		++st;
		return verifB();
	}

	if (dr - st >= 5 && v[st] == '1' && v[st + 2] == '3') // are mai mult de 5 element -> pun 1A3AC
	{
		++st;
		if (!verifA())
			return false;
		st += 2;
		if (!verifA())
			return false;
		++st;
		return verifC();
	}

	return false; // nu merge B :(
}

bool verifC() // C
{
	if (st >= dr)
		return false;

	if (v[st] == '2') // are un element -> 2
		return true;

	if (dr - st >= 3 && v[st] == '1' && v[st + 1] == '2') // are 3 elemente -> pun 12A
	{
		st += 2;
		return verifA();
	}

	if (dr - st >= 3 && v[st] == '3') // aici e complicat. daca are mai mult de 3 elemente as vrea sa gasesc o combinatie de un B si un C care sa dea
	{
		++st;
		if (!verifB())
			return false;
		++st;
		return verifC();
	}

	return false; // nu merge C :(
}

int main()
{
	//ios_base::sync_with_stdio(false);
	//cin.tie(nullptr);
	//cout.tie(nullptr);

	int n, i;

	fin >> n;

	// trebuie o funcitie cre ia un interval st dr din tot vectorul si verifica daca exista ceva care sa intre acolo

	while (n--)
	{
		fin >> dr;

		v.clear();
		for (i = 0; i < dr; ++i)
		{
			int x;
			fin >> x;
			v += ('0' + x);
		}
		st = 0;
		if (verifA() && st == dr - 1)
		{
			fout << "1\n";
			continue;
		}

		st = 0;
		if (verifB() && st == dr - 1)
		{
			fout << "1\n";
			continue;
		}

		st = 0;
		if (verifC() && st == dr - 1)
		{
			fout << "1\n";
			continue;
		}

		fout << "0\n";
		// sa vezi ca trebe mai eficient ...
	}
	
	return 0;
}