// 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>
const int LMAX = 10011;
const int SIRMAX = 500001;

int N, L;
char l[LMAX];
char e[LMAX];
char cpy[LMAX];
char c[SIRMAX];
int x=0,curent=0,b=0,r=0,de=0;
void lit(int i);

void citire()
{
	int x = 0, nr = 0;
	L = 0;
	gets(c);
	for(int i = 0 ; c[i] && c[i] != '\n' && c[i] != EOF ; i++)
		if(c[i] == ' ')
		{
			if(!L)
				L = x;
			else
				l[++nr] = x;
			x = 0;
		}
		else
			x = 10 * x + c[i] - '0';
	if(x)
		l[++nr] = x;		
}

int bac()
{
	for(int i = 1 ; i <= L ; i++)
	{
		if(e[i]=='A' || e[i] == 'B' || e[i]=='C')
			lit(i);
		if(e[i] != l[i])
			return 0;
	}
	if(e[L+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,L);
				e[i]=1;
				e[i+1]='A';
				e[i+2]=3;
				e[i+3]='A';
				e[i+4]='C';
				memcpy(e+i+5,cpy,L);
			}
			else
			{
				memcpy(cpy,e+i+1,L);
				e[i]=2;
				e[i+1]='B';
				memcpy(e+i+2,cpy,L);
			}
		
		}
		else if(e[i]=='C')
		{
			if(l[i]==1)
			{
				memcpy(cpy,e+i+1,L);
				e[i]=1;
				e[i+1]=2;
				e[i+2]='A';
				memcpy(e+i+3,cpy,L);
			}
			else if(l[i]==2)
				e[i]=2;
			else
			{
				memcpy(cpy,e+i+1,L);
				e[i]=3;
				e[i+1]='B';
				e[i+2]='C';
				memcpy(e+i+3,cpy,L);
			}
			
		}

}

int main()
{

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

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

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

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

	}


	return 0;
}