#include <stdio.h>
#define Max 10001
#define FOR(i, a, b) for (i = (a); i <= (b); i++)

int T, L, N;
int a[Max], pos;
char q[Max];
char perla;

int process()
{

    while (N)
    {
	perla = q[N]; N--;

	if (pos > L) return 0;

	if (perla == 'B')
	{
	    if (a[pos] == 1)
	    {
		if (pos + 4 > L) return 0;
		if (a[pos + 2] == 3)
		    q[++N] = 'C', pos += 4;
		else             return 0;
	    }
	    else if (a[pos] == 2)
		q[++N] = 'B', pos += 1;
	    else                 return 0;
	}
	if (perla == 'C')
	{
	    if (a[pos] == 2) pos++;
	    else if (a[pos] == 3) q[++N] = 'C', q[++N] = 'B', pos += 1;
	    else if (a[pos] == 1)
	    {
		if (pos + 2 > L) return 0;
		if (a[pos + 1] == 2)
		    pos += 3;
		else             return 0;
	    }
	}
    }
    if (pos > L) return 1;
    return 0;
}
                
int main()
{
    int i, j;
    FILE *fin = fopen("perle.in", "rt");
    FILE *fout = fopen("perle.out", "wt");
    fscanf(fin, "%d", &T);
    for (i = 1; i <= T; i++)
    {
        fscanf(fin, "%d", &L);
	for (j = 1; j <= L; j++) fscanf(fin, "%d", &a[j]);
	//for (j = 1; j <= L; j++) fprintf(fout, "%d ", a[j]);
	if (L == 1) fprintf(fout, "1\n");
	if (L == 1) continue;

	N = 1; q[N] = 'B'; pos = 1;
	int x1 = process();

	N = 1; q[N] = 'C'; pos = 1;
	int x2 = process();

	if (x1 || x2) fprintf(fout, "1\n");
	else          fprintf(fout, "0\n");
    }
    fclose(fin);
    fclose(fout);

    return 0;
}