#include <iostream>
#include <vector>
#include <string>
#include <fstream>
using namespace std;


ifstream in("perle.in");
ofstream out("perle.out");


bool B(vector<int>& v, int& s);
bool C(vector<int>& v, int& s);

bool C(vector<int>& v, int& s) {
	if (v[s - 1] == 2 ) { return 1; }
	else if (s+2 <= v.size()) {
		if (v[s + 2 - 2] == 2 && v[s + 2 - 3] == 1) {
			s += 2;
			return 1;
		}
		else if (v[s - 1] == 3) { 
			s += 1;
			if (B(v, s)) {
				s += 1;
				return C(v, s);
			}
			else { return 0; }
		}
		else { return 0; }
	}
	else { return 0; }
}



bool B(vector<int>& v,int& s) {
	if (s + 1 < v.size()) {
		if (v[s - 1] == 2) {
			s += 1;
			return B(v, s);
		}
		else if (s + 4 <= v.size()) {
			s += 4;
			if (v[s-5] == 1 && v[s-3] == 3) {
				return C(v, s);
			}
			else { return 0; }
		}
		else { return 0; }
	}
	else { return 0; }
}


int perle(vector<int>& v,int& s) {
	if (v.size() == 1) { s = 1;return 1; }
	else if (v.size() == 2 || v.size() == 4) { return 0; }
	else if (v.size() == 3) {
		if (v[0] == 1 && v[1] == 2) { s = 3; return 1; }
		else { return 0; }
	}
	else if (v[0] == 1 && v[2]==3) {
		s = 5;
		if (v[v.size() - 1] == 2 && v.size()==s) { return 1; }
		else if (v[v.size() - 2] == 2 && v[v.size() - 3] == 1 && v.size()==s+2) { return 1; }
		else if(s < v.size()){
			if (v[s - 1] == 3) {
				s += 1;
				if (B(v, s)) {
					s += 1;
					return C(v, s);
				}
				else { return 0; }
			}
			else { return 0; }
		}
		else { return 0; }
	}
	else if (v[0] == 2) {
		s = 2;
		return B(v, s);
	}
	else if (v[0] == 3) {
		s = 2;
		if (B(v, s)) {
			s += 1;
			return C(v, s);
		}
		else { return 0; }
	}
	else { return 0; }

}

int main()
{
	int N,n,nr,s=0;
	vector<int> v;
	in >> N;
	for (int i = 0;i < N;i++) {
		in >> n;
		if (n == 0) { out << 0 << endl;continue; }
		for (int j = 0;j < n;j++) {
			in >> nr;
			if (nr < 1 || nr > 3) { v.push_back(8);v.push_back(8);v.push_back(8);v.push_back(8);}
			v.push_back(nr);
		}
		if (perle(v, s) == 1 && s == v.size()) { out << 1 << endl; }
		else { out << 0 << endl; }
		
		v.clear();
	}

	return 0;
}