#include <stdio.h>

#define nm 10010

int s[nm], v[nm];
int i, l, ok, dc;

void read()

{
	scanf("%d ", &l);
	for (i=1; i<=l; i++)
	{
		scanf("%d ", &v[i]);
		s[i] = 0;
	}
}


void solve()

{
	ok = 0;
	dc = 0;
if (l > 1)
{
	ok = 1;
	s[1] = 5;
	for (i=1; i<=l && ok == 1; i++)
	{
				if (s[i] == 5)
		{
			if (v[i] == 2)
			{
				if (l - i < 5)
					ok = 0;
				else
				{
					s[i + 1] = 5;
				}
			}
			else
			if (v[i] == 1)
			{
				if (l - i >= 5 && v[i + 2] == 3)
				{
					s[i + 4] = 6;
					i += 3;
				}
				else
				{
					ok = 0;
				}
			}
			else
			{
				ok = 0;
			}
		}
		else
		if (s[i] == 6)
		{
			if (v[i] == 2)
			{
				if (i != l && dc == 0)
					ok = 0;

			}
			else
			if (v[i] == 3)
			{
				if (v[i + 1] == 2)
				{
					s[i + 1] = 5;
					dc += 1;
				}
				else
				if (v[i + 1] == 1 && v[i + 3] == 3)
				{
					s[i + 5] = 6;
                    i += 4;
					dc += 1;
				}
			}
			else
			if (v[i] == 1 && v[i + 1] == 2 && ((l - i) == 2))
			{
				i = l;
			}
			else
            if (v[i] == 1 && v[i + 1] == 2 && dc > 0)
            {
                i += 2;
            }
            else
				ok = 0;
		}
		else
		{
			if (dc > 0)
			{
/*             int j;
             for (j=1; j<=dc; j ++)
                 s[j + i - 1] = 6;*/
				s[i] = 6;
				i --;
				dc --;
			}
			else
				ok = 0;
		}
	}
	if (!ok)
	{
	s[1] = 6;
	ok = 1;
	for (i=1; i<=l && ok == 1; i++)
	{
		if (s[i] == 5)
		{
			if (v[i] == 2)
			{
				if (l - i < 5)
					ok = 0;
				else
				{
					s[i + 1] = 5;
				}
			}
			else
			if (v[i] == 1)
			{
				if (l - i >= 5 && v[i + 2] == 3)
				{
					s[i + 4] = 6;
					i += 3;
				}
				else
				{
					ok = 0;
				}
			}
			else
			{
				ok = 0;
			}
		}
		else
		if (s[i] == 6)
		{
			if (v[i] == 2)
			{
				if (i != l && dc == 0)
					ok = 0;

			}
			else
			if (v[i] == 3)
			{
				if (v[i + 1] == 2)
				{
					s[i + 1] = 5;
					dc += 1;
				}
				else
				if (v[i + 1] == 1 && v[i + 3] == 3)
				{
					s[i + 5] = 6;
                    i += 4;
					dc += 1;
				}
			}
			else
			if (v[i] == 1 && v[i + 1] == 2 && ((l - i) == 2))
			{
				i = l;
			}
			else
            if (v[i] == 1 && v[i + 1] == 2 && dc > 0)
            {
                i += 2;
            }
            else
				ok = 0;
		}
		else
		{
			if (dc > 0)
			{
/*             int j;
             for (j=1; j<=dc; j ++)
                 s[j + i - 1] = 6;*/
				s[i] = 6;
				i --;
				dc --;
			}
			else
				ok = 0;
		}
	}
	}
}
else
{
	ok = 1;
}
}


void write()

{
	if (ok)
		printf("1\n");
	else
		printf("0\n");
}


int main()

{
	freopen("perle.in", "r", stdin);
	freopen("perle.out","w",stdout);
	
	int T;
	scanf("%d", &T);
	for (; T>0; T--)
	{
		read();
		solve();
		write();
	}
	
	fclose(stdin);
	fclose(stdout);

	return 0;
}