#include <stdio.h>
#define MAX 10001

int sir[MAX];
int len;

int test_c(int poz);
int test_b(int poz) 
{
	// B-> 22..21A3AC
	for(;poz <= len && sir[poz] == 2; ++poz); // B->2B
	if(poz + 4 > len) return 0; 
	if(sir[poz] == 1 && sir[poz+2] == 3) return test_c(poz+4); //B->1A3AC
	return 0;
}

int test_c(int poz)
{
	int index;
	if(sir[poz] == 2) return poz; //C -> 2
	if(poz+2<=len && sir[poz] == 1 && sir[poz+1] == 2) return poz+2; // C -> 12A
	if(sir[poz] == 3) // C -> 3BC
	{
		index = test_b(poz+1);
		if(index == 0 || index >= len) return 0;
		return test_c(index+1);
	}
	return 0;
}

int test()
{
	if(len == 1) return 1;
	if(test_b(1) == len || test_c(1) == len) return 1;
	return 0;
}

int main()
{
	int t, i, ok;
	
	freopen("perle.in", "r", stdin);
	freopen("perle.out", "w", stdout);
	
	scanf("%d", &t);
	while(t--)
	{
		scanf("%d", &len);
		for(i = 1; i <= len; ++i)
			scanf("%d", &sir[i]);
		printf("%d\n", test());
	}
	return 0;
}