#include <cstdio>
#include <fstream>

using namespace std;

int n;
int a[16384];
int c (int x);

inline int b (int x){
	
	if(x>n||x<0)
		return -1;
	if(a[x]==2)
		return b(x+1);
	if(a[x]==1&&a[x+2]==3)
		return c(x+4);
	
	return -1;}
	
inline int c (int x){
		
	if(x>n||x<0)
		return -1;
	if(a[x]==2)
		return x+1;
	if(a[x]==1){
		if(a[x+1]==2)
			return x+3;
		else
			return -1;
	}
		
		return c(b(x+1));}

int main ()
{
	
	ifstream in ("perle.in");
	freopen ("perle.out","w",stdout);
	int x,t;
	for(in>>t;t;--t){
			in>>n;
			for(int i=0;i<n;++i)
				in>>a[i];
			if(n==1)
				printf("1\n");
			else
				if(n==2)
					printf("0\n");
				else
					if(n==3)
						if(a[0]==1&&a[1]==2)
							printf("1\n");
						else
							printf("0\n");
					else{
						if(a[0]==1||a[0]==2)
							x=b(0);
						else
							x=c(0);
						printf("%d\n",(x==n?1:0));
						}
		}
	
	return 0;}