#include<fstream>

using namespace std;

int main(){
	ifstream fin("perle.in");
	ofstream fout("perle.out");
	int n,i,l,x[10003],k,m,y[20000];
	bool ver;
	fin>>n;
	for (;n>0;n--){
		fin>>l;
		for (i=0;i<l;i++)
			fin>>x[i];
		k=1;
		if (l==1)
			fout<<"1\n";
		else{
			if (x[0]==1)
				if (l>3)
					y[0]=-2;
				else
					y[0]=-3;
			else
				if (x[0]==2)
					y[0]=-2;
				else
					y[0]=-3;
			ver=true;
			for (i=0;((i<l)&&(i<k))&&(ver);i++){
				if (y[i]<0)
					if (y[i]==-1)
						y[i]=x[i];
					else
						if (y[i]==-2)
							if (x[i]==1){
								for (m=k-1;m>i;m--)
									y[m+4]=y[m];
								y[i]=1;
								y[i+1]=-1;
								y[i+2]=3;
								y[i+3]=-1;
								y[i+4]=-3;
								k+=4;
							}
							else
								if (x[i]==2){
									for (m=k-1;m>i;m--)
										y[m+1]=y[m];
									y[i]=2;
									y[i+1]=-2;
									k++;
								}
								else
									ver=false;
						else{
							if (x[i]==2)
								y[i]=2;
							else
								if (x[i]==1){
									for (m=k-1;m>i;m--)
										y[m+2]=y[m];
									y[i]=1;
									y[i+1]=2;
									y[i+2]=-1;
									k+=2;
								}
								else{
									for (m=k-1;m>i;m--)
										y[m+2]=y[m];
									y[i]=3;
									y[i+1]=-2;
									y[i+2]=-3;
									k+=2;
								}
						}
				else
					if (x[i]!=y[i])
						ver=false;
				if (k>l)
					ver=false;
			}
			if (k!=l)
				ver=false;
			if (ver)
				fout<<"1\n";
			else
				fout<<"0\n";
		}
	}
	fout.close();
}