#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>

using namespace std;
 
ifstream in("perle.in");
ofstream out("perle.out");

char v[10001];

int B(int ind);
int C(int ind);

int B(int ind) {
	if (v[ind] == '2') {
		return B(ind + 1);
	}
	else if (v[ind] == '1' && v[ind + 2] == '3') {
		return C(ind + 4);
	}
	return 0;
}

int C(int ind) {
	if (v[ind] == '2') {
		return ind;
	}
	else if (v[ind] == '3') {
		return C(B(ind+1));
	}
	else if(v[ind] == '1' && v[ind+1] == '2'){
		return ind+2;
	}
	return 0;
}

int main()
{
	int n;
	in >> n;
	for (int i = 1; i <= n; i++) {
		int l;
		in >> l;
		memset(v, 0, 10001);
		for (int j = 1; j <= l; j++) {
			in >> v[j];
		}
		if (l == 1) {
			out << 1 << '\n';
		}
		else if (B(1)==l || C(1)==l) {
			out << 1 << '\n';
		}
		else {
			out << 0 << '\n';
		}
	}
    return 0;
}