#include <stdio.h>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <algorithm>
#include <utility>
#include <string>
#include <functional>
#include <sstream>
#include <fstream>
using namespace std;
#define FOR(i,a,b) for (typeof a i=a;i<=b;i++)
#define fori(it,v) for (typeof ((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define mp make_pair
#define fs first
#define ss second
#define all(c) c.begin(),c.end()
#define pf push_front
#define popb pop_back
#define popf pop_front
ofstream fout;
ostringstream out;
istringstream in;
void initializare_citire()
{
	ifstream fin;
	fin.open("perle.in",ifstream::in);
	fout.open("perle.out",ofstream::out);
	string aux;
	getline(fin,aux,'\0');
	in.str(aux);
	fin.close();
}
void scriere()
{
	fout<<out.str();
	fout.close();
}
int  n, p[10000], nr, ok, poz;
void b();
void c();
void b()
{
	if (poz+1<nr && p[poz]==2)
 	{
		poz++;
		 b();
	}
	else
	 	if (poz+4<nr && p[poz]==1 && p[poz+2]==3)
 			{
				poz+=4;
				c();
			 }
		else
		 ok=0;
}
void c()
{
	if (poz+2<nr && p[poz]==3)
	{
		poz++;
		b();
 		c();
	}
	else
		 if (nr-3==poz && p[poz]==1 && p[poz+1]==2)
			 ok= 1;
		else
			if (poz==nr-1 && p[poz]==2)
			  ok=1;
		else
			if (p[poz]==1 && p[poz+1]==2)
				 poz+=3;
		else
			if (p[poz]==2)
			 	poz++;
			else
				ok=0;
}
int main()
{
	initializare_citire();
	int i, j;
	char init;
	in>>n;
	for (i=0; i<n; i++)
		{
			init='\0';
			ok=0;
			in>>nr;
			for (j=0; j<nr; j++)
				in>>p[j];
			if (nr==1) 
			{
				out<<"1\n";
				break;
			 }
			else
				 if (nr==3 && p[0]==1 && p[1]==2)
					init='C';
				 else
					 if (nr>1 && p[0]==2)
						 init='B';
					else
						if (nr>3 && p[0]==1)
							init='B';
						else
							if (nr>1 && p[0]==3)
								init='C';
			if (init=='\0')
			{
				out<<"0\n";
 				break; 
			}
			poz=0;
			if (init=='B')
				b();
			else
				if (init=='C')
					 c();
			ok?out<<"1\n":out<<"0\n";

		}
	scriere();
	return 0;
}