#include <iostream>
#include <cstdio>

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 == 2]
			&& 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;

	cout << ans << endl;
}

int main()
{
	int T;

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

	cin >> T;

	while (T--) run_test();

	return 0;
}