#include <bits/stdc++.h>

using namespace std;

struct sir{
	string s;
	int l;
};

int n;
sir A[12];

bool eC (int i,int j);

bool eB(int i,int j){
	int ic=j;
	if(A[i].s[ic]=='2'){
		//cout<<2<<'\n';
		return eB(i,ic+1);
	} else if(A[i].s[ic]=='1' && A[i].l>ic+4 && A[i].s[ic+2]=='3'){
		ic+=4;
		//cout<<"1A3A"<<'\n';
		return eC(i,ic);
	}
	return 0;
}

bool eC(int i,int j){
	int ic=j;
	//cout<<j<<'\n';
	if(A[i].s[ic]=='2' && A[i].l==ic+1) return 1;
	else if(A[i].s[ic]=='1' && A[i].s[ic+1]=='2' && A[i].l==ic+3) return 1;
	else if(A[i].s[ic]=='3' && A[i].l>ic+2) return eB(i,ic+1) && eC(i,ic+2);
	return 0;
}

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

int main(){
	fin>>n;
	for(int i=0;i<n;i++){
		char c;
		fin>>A[i].l;
		for(int j=0;j<A[i].l;j++){
			fin>>c;
			A[i].s+=c;
		}
	}
	//for(int i=0;i<n;i++) cout<<A[i].s<<'\n';
	for(int i=0;i<n;i++)
	if(A[i].l == 1){
		fout<<1<<'\n';
	}else if(A[i].l>3){
		fout<<(eC(i,0)||eB(i,0));
		fout<<'\n';	
	} else fout<<0<<'\n';
	return 0;
}