#include <bits/stdc++.h>

using namespace std;

struct sir{
	string s;
	int l;
};

int n,ic=0;
sir A[12];

bool eC (int i);

bool eB(int i){
	if(A[i].s[ic]=='2' && A[i].l>ic+1){
		ic++;
		return eB(i);
	} else if(A[i].s[ic]=='1' && A[i].l>ic+4 && A[i].s[ic+2]=='3'){
		ic+=4;
		return eC(i);
	}
	return 0;
}

bool eC(int i){
	if(A[i].s[ic]=='2' && A[i].l>=ic+1){
		ic++;
		return 1;
	} 
	else if(A[i].s[ic]=='1' && A[i].s[ic+1]=='2' && A[i].l>=ic+3){
		ic+=3;
		return 1;
	} 
	else if(A[i].s[ic]=='3' && A[i].l>ic+2){
		 ic++;
		 bool f = eB(i);
		 ic++;
		 return f && eC(i);
	}
	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) | eB(i));
		fout<<'\n';	
	} else fout<<0<<'\n';
	return 0;
}