#include<fstream.h>
int main ()
{
	ifstream fcin("perle.in");
	ofstream fcout("perle.out");
	int i,j,l,lg,n,ok,v[10003],w[10100],lg2;
	fcin>>n;
	for(i=1;i<=n;i++)
	{
	 fcin>>lg;
	 for(j=1;j<=lg;j++)
		fcin>>v[j];
	 if (lg==1) fcout<<'1'<<'\n';
	 else if (lg==2) fcout<<'0'<<'\n';
	 else if (lg==3){if(v[1]==1&&v[2]==2)fcout<<'1'<<'\n';
					 else fcout<<'0'<<'\n';}
	 else {if(v[1]==1)
			{w[2]='A';w[3]=3;w[4]='A';w[5]='C';lg2=5;}
		   else if (v[1]==2)
			{w[2]='B';lg2=2;}
		   else {w[2]='B';w[3]='C';lg2=3;}
		   ok=0;j=2;
		   while(ok==0)
			   {if(w[j]=='A')j++;
			    else if(w[j]=='C'&&v[j]==1)
					   {for(l=lg2;l>=j+1;l--)
							{w[l+2]=w[l];}
						 w[++j]=2;w[j+1]='A';lg2=lg2+2;}
				else if(w[j]=='C'&&v[j]==2)
						 j++;
				else if(w[j]=='C'&&v[j]==3)
					   {for(l=lg2;l>=j+1;l--)
							{w[l+2]=w[l];}
						 w[++j]='B';w[j+1]='C';lg2=lg2+2;}
				else if(w[j]=='B'&&v[j]==2)
						{for(l=lg2;l>=j+1;l--)
							{w[l+1]=w[l];}
						 w[++j]='B';lg2++;}
				else if (w[j]=='B'&&v[j]==1)
					   {for(l=lg2;l>=j+1;l--)
							{w[l+4]=w[l];}
						 w[++j]='A';w[j+1]=3;w[j+2]='A';w[j+3]='C';lg2=lg2+4;}
				else if(w[j]==v[j])j++;
				else {ok=0;break;}
				if(lg2>lg){ok=0;break;}
				if(lg2==lg&&j==lg+1){ok=1;break;}
				if(lg2<lg&&j==lg2+1){ok=0;break;}
			   }
			if(ok==0)fcout<<'0'<<'\n';
			else fcout<<'1'<<'\n';
		}
	}
	return 0;
}