#include <cstdio>
#define FIN "perle.in"
#define FOUT "perle.out"
#define MAX 10001

long A[MAX];
long T, N, ok, x;

int eval(char c) {
	if ( c=='A' )
		return 1;
	if ( c=='B' ) {
		if ( A[x]==2 ) { // B -> 2B
			if ( x<N-1 ) { 
				++x;
				return eval('B');
			}
			else
				return 0;
		}
		if ( A[x]==1 ) { // B -> 1A3AC 
			 if ( A[x+2] == 3 && x<N-4 ) {
				 x+=4;
				 return eval('C');
			 }
			 else return 0;
		}
		return 0;
	}
	if ( c=='C' ) {
		if ( A[x]==2 )
			return 1;
		if ( A[x]==3 ) { // C -> 3BC
			long ok1 = 0, ok2 = 0;
			if ( x<N-1 ) {
				x++;
				ok1 = eval('B');
			}
			else
				return 0;

			if ( x<N-1 ) {
				++x;
				ok2 = eval('C');
			}
			else
				return 0;
			return ok1 && ok2;
		}
		if ( A[x]==1 && A[x+1]==2 && x<N-2) { // C -> 12A
			x+=2;
			return 1;
		}
	}
	return 0;
}

int main() {
	long i;
	
	freopen(FIN, "r", stdin);
	freopen(FOUT, "w", stdout);
	
	scanf("%ld", &T);
	while (T--) {
		scanf("%ld", &N);
		for (i=0; i<N; ++i)
			scanf("%ld", A+i);
		if ( N==1 ) {
			ok = 1;
		}
		else {
			x=0;
			if ( A[0]==2 ) 
				ok = eval('B');
			if ( A[0]==3 ) {
				ok = eval('C');
               }
			if ( A[0]==1 ) {

				ok = eval('B');
				if ( !ok )
					x=0, ok = eval('C');
			}
		}
          if ( x<N-1 )
	          ok=0;
		printf("%ld\n", ok);
	}
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}