#include <bits/stdc++.h>

using namespace std;

ifstream fin("perle.in");
ofstream fout("perle.out");
int t, a[10005], n,st[10005],top, ok;
/// in stiva pun pietrele A - 1, B - 2, C - 3
int main()
{
	int i, x;
	fin >> t;
	while (t--)
	{
		fin >> n;
		for (i = 1; i <= n; i++)
			fin >> a[i];
		if (n == 1) fout << "1\n";
		else if (n == 3 and a[1] == 1 and a[2] == 2) fout << "1\n";
		else if (n == 3) fout << "0\n";
		else
		{
			top = 1;
			ok = i = 1;
			if (a[i] == 3)
				st[++top] = 3;
			else st[++top] = 2;

			while (top and ok == 1)
			{
				x = st[top];
				top--;
				if (x == 2)
				{
					if (a[i] == 2)
					{
						i++;
						st[++top] = 2;
					}
					else if (a[i] == 1 and a[i + 2] == 3)
					{
						st[++top] = 3;
						i += 4;
					}
					else ok = 0;
				}
				else if (x == 3)
				{
					if (a[i] == 2)
						i++;
					else if (a[i] == 1 and a[i + 1] == 2)
						i += 3;
					else if (a[i] == 3)
					{
						i++;
						st[++top] = 3;
						st[++top] = 2;
					}
					else ok = 0;
				}
			}
			if (i < n or top)
				ok = 0;
			fout << ok << "\n";
		}
	} 


	return 0;
}