#include<stdio.h>
	FILE *f , *g ;
	int n , l , v[10001]  , sw ;
	
	int valid(int i);
	void valid_b(int i);
	void valid_c(int i);
	
	int main()
	{
		f=fopen("perle.in" , "r" );
		g=fopen("perle.out" , "w" );
		fscanf(f , "%d" , &n );
		for ( int i = 1 ; i<= n ; ++i )
		{
			sw = 1;
			fscanf(f , "%d" , &l );
			for ( int j = 1 ; j <= l ; ++j )
				fscanf(f , "%d" , &v[j] );
			fprintf(g , "%d\n" , valid(i));
		}
		fclose(f);
		fclose(g);
		return 0;
	}
	
	int valid(int i)
	{
		if(l == 1)
			return 1;
		if(l == 2)
			return 0;
		if( l == 3 && (v[1]!=1 || v[2]!= 2))
			return 0;
		if(v[1] == 2)
			valid_b(2);
		if(v[1] == 3)
			valid_c(2);
		if(sw)
		return 1;
		return 0;
	}
	
	void valid_b(int i)
	{
		while(v[i] == 2)
			i++;
		if(v[i] != 1 || v[i+2] != 3)
			sw = 0;
		valid_c(i+4);
	}
	void valid_c(int i)
	{
		if(v[i] == 3)
		{
			valid_b(i+1);
			valid_c(i+1);
		}
		if(v[i] != 1 || v[i+1] != 2 )
			sw = 0;
	}