#include	<iostream>
#include	<fstream>
#include	<string.h>
#include	<vector>
using namespace std;
int sepoate=0,nr2,nr3, nu;
unsigned i,p,n,m,j,nr,l,k;
	ifstream f ("perle.in");
	ofstream g ("perle.out");
	vector <short> v;				//    a=4; b=5; c=6        
								   	//	  A -> 1 | 2 | 3
   								    //    B -> 2B | 1A3AC
      								//    C -> 2 | 3BC | 12A
	vector <short> perle;
int primadata()
{
 switch(v[1])
	{
	case 3: if (1==m) {  sepoate=1; break;} else
											{perle.push_back(3); 
											 perle.push_back(5); 
											 perle.push_back(6);} break;
	case 2: if (1==m) {  sepoate=1; break;} else 
												{perle.push_back(2); 
												 perle.push_back(5);}  break;
	case 1: if (1==m) {  sepoate=1; break;} else  if 	(m>5)      {perle.push_back(1);
															  		perle.push_back(4);
															  		perle.push_back(3);
															  		perle.push_back(4);
															  		perle.push_back(6);} 
													else if ((m==5)&&(v[3]==3)&&(v[5]==2))
													{
														sepoate=1;
														break;
													} else
												   if 	((m==3)&&(v[2]==2))
												    {
												   		sepoate=1;
												   		break;
													} else
													{
														sepoate=-1;
														break;
													}
															  break;
	}
	return 0;	
}
int verifica()
{
	nr2=nr3=0;
	nu=0; p=1;
while((p<perle.size())&&(nu==0)&&(perle.size()<=v.size()))
		{
		{switch (perle[p])
			{
				case 4: perle[p]=v[p]; p++;  break;
				case 5: if ((v[p]==2)&&(m-p>=5)) {
							perle.push_back(NULL);
							for (k=perle.size()-1; k>p+1;k--)
								perle[k]=perle[k-1];
							perle[p]=2;
							perle[p+1]=5;
							p++;} else
						{if ((v[p]==1)&&(m-p>=4))
						{	perle.push_back(NULL); perle.push_back(NULL); perle.push_back(NULL); perle.push_back(NULL);
							for (k=perle.size()-1; k>p+4;k--)
								perle[k]=perle[k-4];
							perle[p]=1;
							perle[p+1]=4;
							perle[p+2]=3;
							perle[p+3]=4;
							perle[p+4]=6;
							p++;
						} 
						else {nu=-1;}} break;
				case 6: if (v[p]==2) 
							{perle[p]=2;
							 p++;
							} 	
						else if((v[p]==1)&&(v[p+1]==2))  
									{
							perle.push_back(NULL); perle.push_back(NULL);
							for (k=perle.size()-1; k>p+2;k--)
									perle[k]=perle[k-2];
							perle[p]=1;
							perle[p+1]=2;
							perle[p+2]=4;
							p+=2;	
									} 
										  else if(v[p]==3)
										  	{
											perle.push_back(NULL); perle.push_back(NULL);
												for (k=perle.size()-1; k>p+2;k--)
												perle[k]=perle[k-2];
												perle[p]=3;
												perle[p+1]=5;
												perle[p+2]=6;
												p++;
											} else
												nu=-1; break;
				default: p++; break;
	}}
	}
	switch (nu){
	case 0: {
	for (i=1; i<v.size();i++)
		nr2=nr2*10+v[i];
	for (i=1; i<perle.size();i++)
		nr3=nr3*10+v[i];
	if (nr3==nr2)
		nu=1;
	else nu=-1;
	return nu; break;}
	default: return nu; break;
}	}
int main() 
{ 
	f>>n;
	unsigned int k;
	for (k=0; k<n; k++)
	{
	int nu=0;
	f>>m;	
	sepoate=0; p=1;
	v.push_back(22);
	perle.push_back(22);
	for (j=1; j<=m; j++)
		{
			f>>nr;
			v.push_back(nr);
		}
	primadata();
	if (sepoate==-1)
		g<<0<<"\n"; else 
	if (sepoate==1)
		g<<1<<"\n"; else  
	{
		switch (verifica())
		{
			case 1: g<<"1"<<"\n"; break;
			default:g<<"0"<<"\n"; break;
		} 
	} 
	perle.clear();
	v.clear();
}
	return 0;
}