#include<stdio.h>
#include<deque>
using namespace std;
deque<int> P,Q;
int A=4,B=5,C=6,L,i,x,t;
void read(),solve(),startQ();
int main()
{
	read();
	solve();
	return 0;
}
void read()
{
	freopen("perle.in","r",stdin);
	freopen("perle.out","w",stdout);
	scanf("%d",&t);
}
void solve()
{
	for(;t;t--)
	{
		P.resize(0);Q.resize(0);
		scanf("%d",&L);
		for(i=1;i<=L;i++)
		{
			scanf("%d",&x);
			P.push_back(x);
		}
		startQ();
		for(;;)
		{
			if(P.empty()||Q.empty())break;
			if(Q.front()==A){P.pop_front();Q.pop_front();continue;}
			if(Q.front()==P.front()){P.pop_front();Q.pop_front();continue;}
			if(Q.front()==B&&P.front()==1)
			{
				Q.pop_front();Q.push_front(C);Q.push_front(A);Q.push_front(3);
				Q.push_front(A);P.pop_front();continue;
			}
			if(Q.front()==B&&P.front()==2){Q.push_front(2);continue;}
			if(Q.front()==C&&P.front()==1)
			{
				Q.pop_front();Q.push_front(A);Q.push_front(2);P.pop_front();continue;
			}
			if(Q.front()==C&&P.front()==2)
			{
				Q.pop_front();P.pop_front();continue;
			}
			if(Q.front()==C&&P.front()==3)
			{
				Q.push_front(B);P.pop_front();continue;
			}
			break;
		}
		if(Q.empty()&&P.empty())printf("1\n");
		else printf("0\n");			
	}
}
void startQ()
{
	if(L==1){Q.push_back(A);return;}
	if(P.front()==3){Q.push_back(C);return;}
	if(L<5){Q.push_back(C);return;}
	Q.push_back(B);
}