//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;
bool sant;

void verif(string s)
{
	if (sant == true)
		return;

	//cout << s << " ";
	if (s.size() > v.size())
		return;

	if (s == v)
	{
		sant = true;
		return;
	}

	for (int i = 0; i < (int)s.size(); ++i)
	{
		if (s[i] == 'A')
		{
			verif(s.substr(0, i) + '1' + s.substr(i + 1));
			if (sant == true)
				return;
			verif(s.substr(0, i) + '2' + s.substr(i + 1));
			if (sant == true)
				return;
			verif(s.substr(0, i) + '3' + s.substr(i + 1));
			if (sant == true)
				return;

			return;
		}
		else if (s[i] == 'B')
		{
			verif(s.substr(0, i) + "2B" + s.substr(i + 1));
			if (sant == true)
				return;
			verif(s.substr(0, i) + "1A3AC" + s.substr(i + 1));
			if (sant == true)
				return;

			return;
		}
		else if (s[i] == 'C')
		{
			verif(s.substr(0, i) + '2' + s.substr(i + 1));
			if (sant == true)
				return;
			verif(s.substr(0, i) + "3BC" + s.substr(i + 1));
			if (sant == true)
				return;
			verif(s.substr(0, i) + "12A" + s.substr(i + 1));
			if (sant == true)
				return;

			return;
		}
	}
}

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

	int n, nr, i;

	fin >> n;

	// as vrea ceva recursiv de ia un sir pe perle si spune fiecare in ce se poate transofma

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

		v.clear();
		for (i = 1; i <= nr; ++i)
		{
			int x;
			fin >> x;
			v += ('0' + x);
		}

		sant = false;
		verif("A");
		verif("B");
		verif("C");

		fout << (int)sant << "\n";
	}
	
	return 0;
}