#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<vector>
using namespace std;

vector<int> st;

void push1B(){
	st.push_back('C');
	st.push_back('A');
	st.push_back(3);
	st.push_back('A');
}

void push3C(){
	st.push_back('C');
	st.push_back('B');
}

void push1C(){
	st.push_back('A');
	st.push_back(2);
}

int main(){
	freopen("perle.in", "r", stdin);
	freopen("perle.out", "w", stdout);
	int N, c, j;
	scanf("%d", &N);
	bool ok;
	for (int i = 0, L; i < N; ++i){
		scanf("%d", &L);
		if (L == 1) {
			scanf("%d", &c);
			printf("1\n");
			continue;
		}
		st.clear();
		scanf("%d", &c);
		switch (c){
			case 1:
				if (L == 3) push1C();
				else push1B();
				break;
			case 2:
				st.push_back('B');
				break;
			case 3:
				push3C();
				break;
		}
		ok = true;
		for (j = 1; j < L; ++j){
			if (!st.size()){
				printf("0\n");
				ok = false;
				break;
			}
			scanf("%d", &c);

			switch (st.back()){
				case 'A':
					st.pop_back();
					break;
				case 'B':
					if (c == 3) ok = false;
					else 
						if (c == 1) {
							st.pop_back();
							push1B();
						}
					break;
				case 'C':
					st.pop_back();
					if (c == 3)	push3C();
					else 
						if (c == 1) push1C();
					break;
				default: 
					if (c == st.back()) st.pop_back();
					else ok = false;
					break;
			}
			if (!ok) break;
		}
		if (j != L - 1) 
			for (; j < L - 1; ++j) scanf("%d", &c);
		if (st.size() || !ok) printf("0\n");
		else if (ok) printf("1\n");
	}
	return 0;
}