// perle.cpp : Defines the entry point for the console application.
//

#include <stdio.h>
#include <algorithm>
#include <list>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <deque>
#include <string>
#include <cassert>
#include <iostream>
#include <iterator>

int n;
char c[1000001];
char l[100001];
char e[100001];
char cpy[100001];
int x=0,nr=0,curent=0,b=0,r=0,de=0;

void lit(int i);

void citire()
{
	x=0;nr=0;
	memset(l,0,100001);
	memset(e,0,100000);
	fgets(c,1000000,stdin);
	for(int i=0;c[i] && c[i]!='\n';i++)
		if(c[i]==' ')
		{
			l[++nr]=x;
			x=0;
		}
		else
			x=10*x+c[i]-'0';
	if(x)
		l[++nr]=x;

}

int bac()
{
	for(int i=1;i<=nr;i++)
	{
		if(e[i]=='A' || e[i]=='B' || e[i]=='C')
			lit(i);
		if(e[i]!=l[i])
			return 0;
	}
	if(e[nr+1])
		return 0;
	else
		return 1;
}



void lit(int i)
{
	
		if(e[i]=='A')
		{
			if(l[i]==1)
				e[i]=1;
			else if(l[i]==2)
				e[i]=2;
			else if(l[i]==3)
				e[i]=3;
		}
		else if(e[i]=='B')
		{
			if(l[i]==1)
			{
				memcpy(cpy,e+i+1,nr);
				e[i]=1;
				e[i+1]='A';
				e[i+2]=3;
				e[i+3]='A';
				e[i+4]='C';
				memcpy(e+i+6,cpy,nr);
			}
			else
			{
				memcpy(cpy,e+i+1,nr);
				e[i]=2;
				e[i+1]='B';
				memcpy(e+i+3,cpy,nr);
			}
		
		}
		else if(e[i]=='C')
		{
			if(l[i]==1)
			{
				memcpy(cpy,e+i+1,nr);
				e[i]=1;
				e[i+1]=2;
				e[i+2]='A';
				memcpy(e+i+4,cpy,nr);
			}
			else if(l[i]==2)
				e[i]=2;
			else
			{
				memcpy(cpy,e+i+1,nr);
				e[i]=3;
				e[i+1]='B';
				e[i+2]='C';
				memcpy(e+i+4,cpy,nr);
			}
			
		}

}

int main()
{

	freopen("perle.in","r",stdin);
	freopen("perle.out","w",stdout);

	scanf("%d\n",&n);

	for(int i=1;i<=n;i++)
	{

		citire();
		e[1]='A';
		if(bac())
		{
			printf("1\n");
			continue;
		}
		e[1]='B';
		if(bac())
		{
			printf("1\n");
			continue;
		}
		e[1]='C';
		if(bac())
			printf("1\n");
		else
			printf("0\n");

	}


	return 0;
}