#include <stdio.h>
#define MAX 10001


struct nod {
	int v[MAX];
	nod * next;
}*first, *last, *p;

int DEBUG = 0;

int sir[MAX];

int expandez(nod *src)
{
	int i, poz = 0;
	nod *p2 = new nod; p2 -> next = NULL;
	int *v = src->v, *v2 = p2->v;
	
	for(i = 1; i <= v[0] && i <= sir[0]; ++i)
		switch(v[i])
		{
		case 'A': v2[++poz] = sir[i];
			break;
		case 'B': 
			if(sir[i] == 2 && sir[0] > i)
			{
				v2[++poz] = 2, v2[++poz] = 'B';
				for(++i; i <= v[0]; ++i)
					v2[++poz] = v[i];
				v2[0] = poz;
				last -> next = p2; last = p2;
				return 0;
			}
			else if(sir[i] == 1 && sir[0] >= i+4 && sir[i+2] == 3)
			{	
				v2[++poz] = 1; v2[++poz] = sir[i+1]; v2[++poz] = 3; v2[++poz] = sir[i+3]; v2[++poz] = 'C';
				for(++i; i <= v[0]; ++i)
					v2[++poz] = v[i];
				v2[0] = poz;
				last -> next = p2; last = p2;
				return 0;				
			}
			else
			{
				delete p2; return 0;
			}
		case 'C':	
			if(sir[i] == 2)
			{
				v2[++poz] = 2;
			}
			else if(sir[i] == 3 && sir[0] >= i+2)
			{
				v2[++poz] = 3; v2[++poz] = 'B'; v2[++poz] = 'C';
				for(++i; i <= v[0]; ++i)
					v2[++poz] = v[i];
				v2[0] = poz;
				last -> next = p2; last = p2;
				return 0;
			}
			else if(sir[i] == 1 && sir[0] >= i+2 && sir[i+1] == 2)
			{
				v2[++poz] = 1; v2[++poz] = 2; v2[++poz] = sir[i+2];
				for(++i; i <= v[0]; ++i)
					v2[++poz] = v[i];
				v2[0] = poz;
				last -> next = p2; last = p2;
				return 0;
			}
			else
			{
				delete p2; return 0;
			}
		default:
			if(v[i] != sir[i]) 
			{
				delete p2; return 0;
			}
			else v2[++poz] = v[i];
		}
	if(v[0] == sir[0]) 
	{
		v2[0]=poz;
		delete p2;
		return 1;
	}
	delete p2;
	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", &sir[0]);
		for(i = 1; i <= sir[0]; ++i)
			scanf("%d", &sir[i]);
		last = new nod; last -> v[0] = 1; last -> v[1] = 'A'; last -> next = NULL;
		p = new nod; p -> v[0] = 1; p -> v[1] = 'B'; p -> next = last;
		first = new nod; first -> v[0] = 1; first -> v[1] = 'C'; first -> next = p;
		ok = 0;
		while(first != NULL && !ok)
		{
			ok = expandez(first); 		
			p = first; first = first -> next;
			delete p;
		}
		if(ok) printf("1\n");
		else printf("0\n");
	}
	return 0;
}