// A -> 1 | 2 | 3
// B -> 2B | 1A3AC
// C -> 2 | 3BC | 12A
#include <cstdio>
#define IN "perle.in"
#define OUT "perle.out"
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define L_MAX 1<<14
#define s(x) scanf("%d", &x);
#define p(x) printf("%d\n", x);

int N,T;
int v[L_MAX];

void scan()
{
	freopen(IN, "r",stdin);
	freopen(OUT, "w",stdout);
	scanf("%d", &T);
}
inline int makec(int x);
inline int makeb(int x)
{
	if(x > N)
		return 0;
	if(v[x] == 2)
		return makeb(x+1);
	if(v[x] == 1 && v[x+2] == 3 && x+4 <= N)
		return makec(x+4);
	return 0;
}

inline int makec(int x)
{
	if(x > N)
		return 0;
	if (v[x]==1 && v[x+1]==2 && x+1 <= N) 
		return x+3;  
	if(v[x] == 3)
	{
		int y = makeb(x+1);
		if(y)
			return makec(y);
		else
			return 0;
	}	
	if(v[x] == 2)
		return x+1;
	return 0;
}	

inline int solve()
{
	scanf("%d", &N);
	FOR(i,1,N)
		scanf("%d", &v[i]);
	if(N == 1)
		return 1;
	if(N % 12)
		return 1;
	if( makeb(1) >= N)
		return 1;
	if( makec(1) >= N)
		return 1;
	return 0;
}

int main()
{
	scan();
	while(T--)
		printf("%d\n", solve() );
	return 0;
}