// 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];
int x=0,nr=0,curent=0,b=0,r=0,de=0;

void citire()
{
	x=0;nr=0;
	memset(l,0,100001);
	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;

}

void back(int k,char e[])
{
	int i=1;
	char a[50001];

	if(de)
		return;

	if(k==nr+1)
	{
		if(!e[0])
			de=1;
		return;
	}

		while(i<=e[0])
		{
			if(e[i]=='A')
			{
				a[0]=e[0];a[1]=1;
				for(int j=2;j<=e[0];j++)
					a[j]=e[j];
				back(k+i-1,a);

				a[0]=e[0];a[1]=2;
				for(int j=2;j<=e[0];j++)
					a[j]=e[j];
				back(k+i-1,a);

				a[0]=e[0];a[1]=3;
				for(int j=2;j<=e[0];j++)
					a[j]=e[j];
				back(k+i-1,a);
			}
			else if(e[i]=='B')
			{
				a[0]=1+e[0];a[1]=2;a[2]='B';
				for(int j=2;j<=e[0];j++)
					a[1+j]=e[j];
				back(k+i-1,a);

				a[0]=4+e[0];a[1]=1;a[2]='A';a[3]=3;a[4]='A';a[5]='C';
				for(int j=2;j<=e[0];j++)
					a[4+j]=e[j];
				back(k+i-1,a);
			}
			else if(e[i]=='C')
			{
				a[0]=e[0];a[1]=2;
				for(int j=2;j<=e[0];j++)
					a[j]=e[j];
				back(k+i-1,a);

				a[0]=2+e[0];a[1]=3;a[2]='B';a[3]='C';
				for(int j=2;j<=e[0];j++)
					a[2+j]=e[j];
				back(k+i-1,a);

				a[0]=2+e[0];a[1]=1;a[2]=2;a[3]='A';
				for(int j=2;j<=e[0];j++)
					a[2+j]=e[j];
				back(k+i-1,a);
			}
			else if(e[i]==l[k])
			{
				a[0]=e[0]-1;
				for(int j=1;j<=a[0];j++)
					a[j]=e[j+1];
				back(k+i,a);
			}
			else
				return;
			i++;
		}

	

}
int main()
{
	char e[50001]={0};

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

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

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

		citire();

		de=0;
		e[0]=1;
		e[1]='A';
		back(1,e);

		if(de)
		{
			printf("1\n");
			continue;
		}

		e[1]='B';
		back(1,e);

		if(de)
		{
			printf("1\n");
			continue;
		}

		e[1]='C';
		back(1,e);

		if(de)
			printf("1\n");
		else
			printf("0\n");

	}


	return 0;
}