#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

int T(0),
	N(0),
	A[10002];
char l[10002];

void movemem(char *l, int start, int count) {
	memcpy(l + start + count, l + start, count);
}

int main(int argc, char *argv[]) {
	ifstream fin("perle.in");
	fin >> T;
	ofstream fout("perle.out");
	for (int t(0); t < T; ++t) {
		fin >> N;
		for (int i(0); i < N; ++i)
			fin >> A[i];
		
		//for (int i(0); i < N; ++i)
		//	cout << A[i];
		//cout << endl;
		
		bool gasit(false);
		
		for (int i(0); i < 3; ++i) {
			memset(l, 0, sizeof(l));
			l[0] = 'A' + i;
			int m(1);
			
			//cout << "--- " << (char)('A' + i) << endl;
			//cout << l << endl;
			int j(0);
			for (; (j < N) && (j < m) && (m < 10001); ++j) {
				/*if (l[j] == A[i] + '0') {
					cout << "Nimic" << endl;
				} else*/ if (l[j] == 'A') {
					//cout << "Schimb A" << endl;
					if ((1 <= A[j]) && (A[j] <= 3))
						l[j] = A[j] + '0';
					else {
						break;
					}
				} else if (l[j] == 'B') {
					//cout << "Schimb B" << endl;
					if (A[j] == 2) {
						l[j] = '2';
						movemem(l, j + 1, 1);
						l[j + 1] = 'B';
						++m;
					} else if (A[j] == 1) {
						l[j] = '1';
						movemem(l, j + 1, 4);
						l[j + 1] = 'A';
						l[j + 2] = '3';
						l[j + 3] = 'A';
						l[j + 4] = 'C';
						m += 4;
					} else {
						break;
					}
				} else if (l[j] == 'C') {
					//cout << "Schimb C" << endl;
					if (A[j] == 2) {
						l[j] = '2';
					} else if (A[j] == 3) {
						l[j] = '3';
						movemem(l, j + 1, 2);
						l[j + 1] = 'B';
						l[j + 2] = 'C';
						m += 2;
					} else if (A[j] == 1) {
						l[j] = '1';
						movemem(l, j + 1, 2);
						l[j + 1] = '2';
						l[j + 2] = 'A';
						m += 2;
					} else {
						break;
					}
				} else if (l[j] != A[j] + '0') {
					break;
				}
			//	cout << l << endl;
			}
			
			/*for (int i(0); i < m; ++i)
				cout << l[i] << " ";
			cout << endl << "---" << m << " " << N << endl;*/
			if (m == N) {
				gasit = true;
				break;
			}
		}
		
		if (gasit)
			fout << 1 << endl;
		else
			fout << 0 << endl;
	}
	fout.close();
	fin.close();
	
	return 0;
}