#include <stdio.h>
#define Nmax 10003

int v[Nmax], N, T, t, i, OK;

void B();
void C();

void B() {
	
	if (i > N) {
		OK = 0;
		return ;
	}
	
	if (v[i] == 2) {
		i++;
		B();
	}
	else if (v[i] == 1 && v[i + 2] == 3) {
		i += 4;
		C();
	}
	else {
		OK = 0;
		return ;
	}
}

void C() {
	
	if (i > N) {
		OK = 0;
		return ;
	}
	
	if (v[i] == 2)
		i++;
	else if (v[i] == 1 && v[i + 1] == 2)
		i += 3;
		else if (v[i] == 3) {
			i++;
			B();
			C();
		}
		else {
			OK = 0;
			return ;
		}
}

int main() {
	
	FILE *f = fopen("perle.in", "r");
	FILE *g = fopen("perle.out", "w");
	
	fscanf(f, "%d", &T);
	
	for (t = 1; t <= T; t++) {
		
		fscanf(f, "%d", &N);
		for (i = 1; i <= N; i++)
			fscanf(f, "%d", &v[i]);
		
		if (N == 1 || (N == 3 && v[1] == 1 && v[2] == 2)) {
			fprintf(g, "1\n");
			continue;
		}
		
		OK = 1;
		if (v[1] == 2) {
			i = 2;
			B();
		}
			else if (v[1] == 1 && v[3] == 3) {
				i = 5;
				C();
			}
				else if (v[1] == 3) {
					i = 2;
					B();
					C();
				}
		
		if (i != N + 1)
			OK = 0;
		
		fprintf(g, "%d\n", OK);
	}
	
	
	fclose(f);
	fclose(g);
	
	return 0;
}