#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;
	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 if (((v[2]==2)&&(m>7))||((v[2]==1)&&(m>=7)))
											{perle.push_back(3); 
											 perle.push_back(5); 
											 perle.push_back(6);} break;
	case 2: if (1==m) {  sepoate=1; break;} else if (((v[2]==2)||((v[2]==1)&&(v[4]==3)&&(m>=6)))&&(m>=5))
												{perle.push_back(2); 
												 perle.push_back(5);} 
												  else {sepoate=-1; break;} 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;
while((p<=perle.size())&&(nu!=-1)&&(perle.size()<=m+1))
		switch (perle[p])
			{
				case 4: perle[p]=v[p]; p++;  break;
				case 5: if ((v[p]==2)&&(m-p>=5)) {
							perle.pop_back();
							perle.push_back(2); 
							perle.push_back(5);
							p++;} else
						if ((v[p]==1)&&(m-p>=4))
						{
							perle.pop_back();
							perle.push_back(1);
							perle.push_back(4);
							perle.push_back(3);
							perle.push_back(4);
							perle.push_back(6);
							p++;
						} 
						else nu=-1; break;
				case 6: if (v[p]==2) 
							{perle.pop_back(); 
							 perle.push_back(2);
							 p++;
							} 	
						else if((v[p]==1)&&(v[p+1]==2))  
									{
										perle.pop_back();
										perle.push_back(1);
										perle.push_back(2);
										perle.push_back(4);
										p+=2;	
									} 
										  else if((v[p]==3)&&(m-p)>=6)
										  	{
												perle.pop_back();
												perle.push_back(3);
												perle.push_back(5);
												perle.push_back(6);
												p++;
											} else
												nu=-1; break;
				default: p++; break;
	}
	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;
}	
int main() 
{ 
	ifstream f ("perle.in");
	ofstream g ("perle.out");
	f>>n;
	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;
}