#include <stdio.h>
#define nmax 10010
int n,l,vf[2], ok[2];
char s[2][nmax],a;

void read();
void solve();

FILE *f,*g;
int main()
{
	solve();
	return 0;
}

void solve()
{
	int i,j, ai;
	f=fopen("perle.in","rt");
	g=fopen("perle.out","wt");
	fscanf(f,"%d\n",&n);
	while (n--)
		{
			fscanf(f,"%d ",&l);
			if (!(l-1))
				{
					fscanf(f, "%d", &ai);
					fprintf(g,"1\n");
					continue;
				}
			s[0][0]='B';
			s[1][0]='C';
			vf[0]=vf[1]=0;
			ok[0]=ok[1]=1;
			for (j = 0; j <l; j++)
			{
				fscanf(f,"%d", &ai);
				a = ai + '0';

				for (i=0;i<=1;i++)
				{
					if (vf[i] < 0)
						ok[i] = 0;
					if (ok[i])
					{
						if (s[i][vf[i]] == a || s[i][vf[i]] == 'A')
						{
							vf[i]--;
							continue;
						}
						if (s[i][vf[i]] <= '3' && s[i][vf[i]] != a)
						{
							ok[i] = 0;
							continue;
						}
						if (s[i][vf[i]] == 'B')
						{
							if (a == '1')
							{
								vf[i]--;
								s[i][++vf[i]] = 'C';
								s[i][++vf[i]] = 'A';
								s[i][++vf[i]] = '3';
								s[i][++vf[i]] = 'A';
							}
							if (a == '2')
							{
								vf[i]--;
								s[i][++vf[i]] = 'B';
							}
							if (a == '3')
							{
								ok[i] = 0;
							}
						}
						else
						{
							if (a == '1')
							{
								vf[i]--;
								s[i][++vf[i]] = 'A';
								s[i][++vf[i]] = '2';
							}
							if (a == '2')
							{
								vf[i]--;
							}
							if (a == '3')
							{
								vf[i]--;
								s[i][++vf[i]] = 'C';
								s[i][++vf[i]] = 'B';
							}
						}
					}
				}
			}
			fprintf(g, "%d\n", (ok[0] && vf[0] == -1) || (ok[1] && vf[1] == -1));
		}
	fclose(f);
	fclose(g);
}