#include <iostream>
#include <cstdio>
#include <fstream>

using namespace std;

#define NM 10005

int pabbles[NM];
int N;

int is_normal(int nr)
{
	if (nr <= 3) return 1;
	return 0;
}

int is_A(int nr)
{
	if (nr == 4) return 1;
	return 0;
}

int is_B(int nr)
{
	if (nr == 5) return 1;
	return 0;
}

int is_C(int nr)
{
	if (nr == 6) return 1;
	return 0;
}

int tryoutA(int start, int end);
int tryoutB(int start, int end);
int tryoutC(int start, int end);



int tryoutA(int start, int end)
{
	if (start == end)
	{
		if (is_normal(pabbles[start])) return 1;
		if (is_A(pabbles[start])) return 1;
	}

	return 0;
}

int tryoutB(int start, int end)
{
	if (start == end)
		if (is_B(pabbles[start])) return 1;

	if (end - start >= 1)
		if (pabbles[start] == 2 
			&& tryoutB(start + 1, end)) return 1;

	if (end - start >= 4)
		if (pabbles[start] == 1 
			&& tryoutA(start + 1, start + 1) 
			&& pabbles[start+2] == 3
			&& tryoutA(start + 3, start + 3)
			&& tryoutC(start + 4, end)) return 1;

	return 0;		
}

int tryoutBC(int start, int end)
{
	for (int mid = start; mid < end; ++mid)
		if (tryoutB(start, mid) && tryoutC(mid + 1, end)) return 1;
	return 0;
}

int tryoutC(int start, int end)
{
	if (start == end)
		if (pabbles[start] == 2) return 1;

	if (end - start >= 2)	
		if (pabbles[start] == 3
			&& tryoutBC(start + 1, end)) return 1;

	if (end - start == 2)
		if (pabbles[start] == 1
			&& pabbles[start + 1] == 2
			&& tryoutA(start + 2, start + 2)) return 1;

	return 0;
}

void run_test()
{
	cin >> N;
	for (int i = 1; i <= N; ++i) cin >> pabbles[i];
	int ans = 0;
	if (!ans) if(tryoutA(1, N)) ans = 1;
	if (!ans) if(tryoutB(1, N)) ans = 1;
	if (!ans) if(tryoutC(1, N)) ans = 1;

	/*
	if (ans == 0)
	{
		for (int i = 1; i <= N; ++i) cout << pabbles[i] << " ";
			cout << endl;
	}
	*/
	cout << ans << endl;
}

int main(int argc, char *argv[])
{
	/*
	if (argc == 2)
	{
		ifstream fin;
		fin.open("test_perle");
		fin >> N;
		for (int i = 1; i <= N; ++i)
			fin >> pabbles[i];
		fin.close();
		while (1)
		{
			char ch;
			int start, end;
			cin >> ch >> start >> end;
			cout << ch << endl;
			if (ch == 'A') cout << tryoutA(start, end) << endl;
			if (ch == 'B') cout << tryoutB(start, end) << endl;
			if (ch == 'C') cout << tryoutC(start, end) << endl;
			if (ch == 'D') cout << tryoutBC(start, end) << endl;
		}
		return 0;
	}
	*/
	int T;

	freopen ("perle.in", "r", stdin);
	freopen ("perle.out", "w", stdout);

	cin >> T;

	while (T--) run_test();

	return 0;
}