#include <fstream.h>

int n,i,j,v[10002];

int rezolva(char c);

main(){
	freopen("perle.in", "r", stdin);
	freopen("perle.out", "w", stdout);
	scanf("%d", &n);
	for(j=1;j<=n;j++){
		scanf("%d", &v[0]);
		if(v[0]==1){
			scanf("%d", &v[0]);
			printf("1\n");
			continue;}			
		for(i=v[0];i>=1;i--)
			scanf("%d", &v[i]);
		if(v[v[0]]==2)
			printf("%d\n", rezolva('b'));
		else
			printf("%d\n", rezolva('c'));
	}
}

int rezolva(char c){
	if(c=='b'){
		if(v[0]<=0)
			return 0;
		while(v[v[0]]==2)
			v[0]--;
		if(v[0]<5||v[v[0]]!=1||v[v[0]-2]!=3)
			return 0;
		else{
			v[0]-=4;
			return rezolva('c');}}
	else{
		switch(v[v[0]]){
		case 1:
			if(v[v[0]]==1&&v[v[0]-1]==2&&v[0]==3){
				v[0]-=3;
				return 1;}
			else{
				v[0]-=3;
				return 0;}				
			break;
		case 2:
			if(v[0]==1){
				v[0]--;
				return 1;}
			else{
				v[0]--;
				return 0;}
			break;
		case 3:
			v[0]--;
			rezolva('b');
			if(v[0]>0)
				return rezolva('c');
			else 
				return 0;
			break;
		default:
			return 0;}}
}