#include <bits/stdc++.h>

using namespace std;

struct sir{
	string s;
	int l;
};

int n,ic=0;
sir a;

bool eC ();

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

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