#include<stdio.h>
int N,T,nr[10100];
int B(int x);
int C(int x){
	if(x>N || x<0)
		return -1;
	if(nr[x]==2)
		return x+1;
	if(nr[x]==1){
		if(nr[x+1]==2)
			return x+3;
		else
			return -1;
	}
	return C(B(x+1));
}
int B(int x){
	if(x>N || x<0)
		return -1;
	if(nr[x]==2)
		return B(x+1);
	if(nr[x]==1 && nr[x+2]==3)
		return C(x+4);
	return -1;
}
int main(){
	freopen("perle.in","r",stdin);
	freopen("perle.out","w",stdout);
	int i;
	scanf("%d",&T);
	for(;T;--T){
		scanf("%d",&N);
		for(i=0;i<N;++i)
			scanf("%d",&nr[i]);
		if(N==1){
			printf("1\n");
			continue;
		}
		if(N==2){
			printf("0\n");
			continue;
		}
		if(N==3){
			if(nr[0]==1 && nr[1]==2)
				printf("1\n");
			else
				printf("0\n");
			continue;
		}
		if(nr[0]==1 || nr[0]==2)
			i=B(0);
		else
			i=C(0);
		if(i==N)
			printf("1\n");
		else
			printf("0\n");
	}
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}