#include <stdio.h>

int t, l, p, valid[2], stiva[2][10001], niv[2];

int main()
{
	freopen("perle.in","r",stdin);
	freopen("perle.out","w",stdout);
	
	int i;
	
	scanf("%d",&t);
	
	while(t--)
	{
		scanf("%d", &l);
		if(l == 1)
		{
			scanf("%d", &p);
			printf("1\n");
		}
		else
		{
			valid[0] = valid[1] = 1;
			niv[0] = 1;
			niv[1] = 1;
			stiva[0][1] = 5;
			stiva[1][1] = 6;
			while(l--)
			{
				scanf("%d", &p);
				for(i = 0; i < 2; ++i)
				{
					if(valid[i])
					{
						if(stiva[i][niv[i]] < 4)
						{
							if(stiva[i][niv[i]] == p)
							{
								--niv[i];
								if(niv[i] == 0 && l != 0)
								{
									valid[i] = 0;
								}
							}
							else
							{
								valid[i] = 0;
							}
						}
						else if(stiva[i][niv[i]] == 4)
						{
							--niv[i];
							if(niv[i] == 0 && l != 0)
							{
								valid[i] = 0;
							}
						}
						else if(stiva[i][niv[i]] == 5)
						{
							if(p == 1)
							{
								stiva[i][niv[i]] = 6;
								stiva[i][++niv[i]] = 4;
								stiva[i][++niv[i]] = 3;
								stiva[i][++niv[i]] = 4;
							}
							else if(p == 2)
							{
								continue;
							}
							else
							{
								valid[i] = 0;
							}
						}
						else
						{
							if(p == 1)
							{
								stiva[i][niv[i]] = 4;
								stiva[i][++niv[i]] = 2;
							}
							else if(p == 2)
							{
								niv[i]--;
								if(niv[i] == 0 && l != 0)
									valid[i] = 0;
							}
							else
							{
								stiva[i][++niv[i]] = 5;
							}
						}
					}
				}
			}
			if((valid[0] && !niv[0]) || (valid[1] && !niv[1]))
			    printf("1\n");
			else
			    printf("0\n");
		}
	}
	
	return 0;
}