#include<stdio.h>

using namespace std;

int v[10001], L, pos;

void fct (int x, int u[]) {
	int k[10001], i, ok;
	if (u[0] == L) {
		ok = 1;
		for (i = 1; i <= L; ++i)
			if (u[i] != v[i]) {
				ok = 0;
				i = L + 1;
			}
		if (ok == 1) 
			pos = 1;
	}
	if (u[0] != L || u[x] == 4 || u[x] == 6) {
		for (i = 0; i <= u[0]; ++i)
			k[i] = u[i];
		if (k[x] >= 4) {
			if (k[x] == 4) {
				k[x] = 1;
				fct (x, k);
				k[x] = 2;
				fct (x, k);
				k[x] = 3;
				fct (x, k);
				k[x] = u[x];
			}
			else if (k[x] == 5) {
				if (k[0] <= L - 1) {
					k[x] = 2;
					for (i = k[0] + 1; i >= x + 2; --i)
						k[i] = k[i-1];
					k[x + 1] = 5;
					++k[0];
					fct (x, k);
					for (i = 0; i <= u[0]; ++i)
						k[i] = u[i];
				}
				if (k[0] <= L - 4) {
					k[x] = 1;
					for (i = u[0] + 4; i >= x + 5; --i)
						k[i] = k[i - 4];
					k[0] += 4;
					k[x + 1] = 4;
					k[x + 2] = 3;
					k[x + 3] = 4;
					k[x + 4] = 6;
					fct (x, k);
					for (i = 0; i <= u[0]; ++i)
						k[i] = u[i];
				}
			}
			else {
				k[x] = 2;
				fct (x, k);
				if (k[0] <= L - 2) {
					k[x] = 3;
					for (i = u[0] + 2; i >= x + 3; --i)
						k[i] = k[i - 2];
					k[x+1] = 5;
					k[x+2] = 6;
					k[0] += 2;
					fct (x,k);
					for (i = 0; i <= u[0]; ++i)
						k[i] = u[i];
				}
				if (k[0] <= L - 2) {
					k[x] = 1;
					for (i = u[0] + 2; i >= x + 3; --i)
						k[i] = k[i - 2];
					k[x+1] = 2;
					k[x+2] = 4;
					k[0] += 2;
					fct (x,k);
					for (i = 0; i <= u[0]; ++i)
						k[i] = u[i];
				}
			}
		}
		else if (x < u[0]) 
			fct (x+1, u);
	}
}
int main() {
	freopen ("perle.in", "r", stdin);
	freopen ("perle.out", "w", stdout);
	int N, n, i;
	int m[10001];
	scanf ("%d", &N);
	for (n = 1; n <= N; ++n) {
		pos = 0;
		scanf ("%d", &L);
		for (i = 1; i <= L; ++i) 
			scanf ("%d", &v[i]);
		m[0] = 1;
		m[1] = 4;
		fct (1, m);
		if (pos != 1) {
			m[0] = 1;
			m[1] = 5;
			fct (1, m);
			if (pos != 1) {
				m[0] = 1;
				m[1] = 6;
				fct (1, m);
			}
		}
		printf ("%d\n", pos);
	}
	return 0;
}