#include <cstdio>

bool A(int*, int*);
bool B(int*, int*);
bool C(int*, int*);

bool A(int* s, int* f)
{
	return s == f;
}

bool B(int* s, int *f)
{
	if (s >= f) return false;
	if (*s == 2) return B(s + 1, f);
	if (s + 3 < f) if (*s == 1 && *(s + 2) == 3) return C(s + 4, f);
	return false;
}

bool C(int* s, int *f)
{
	if (s > f) return false;
	if (s == f && *s == 2) return true;
	if (*s == 3) return ( B(s + 1, f - 1) && *f == 2 ||
			B(s + 1, f - 3) && C(f - 2, f) );
    if (f - s == 2) return (*s == 1 && *(s + 1) == 2);
    return false;
}

int main()
{
	int N, t, x[10003], i, j;
	FILE *f1 = fopen("perle.in", "r"), *f2 = fopen("perle.out", "w");
	fscanf(f1, "%d\n", &N);
	for (i = 0; i != N; ++i) {
		fscanf(f1, "%d ", &t);
		for (j = 0; j != t; ++j)
            fscanf(f1, "%d ", &x[j]);
        --t;
		fprintf(f2, "%d\n", A(x, x + t) || B(x, x + t) || C(x, x + t));
	}
	fclose(f1);
	fclose(f2);
	return 0;
}