using namespace std;
#include<fstream>
#include<map>
#include<vector>
#include<string>
#define Lmax 10001
int check(vector<char> s,int lg)
{
	int begin=1;
	while(begin<lg-1)
	switch(s[begin])
	{
	case '1':
		{
			if(lg-begin==2)
			{
				if(s[begin+1]='2')
					return 1;
				else
				return 0;
			}
			else
				if(s[begin+3]=='3')
					begin+=4;
				else
					return 0;
			break;
		}
	case'2':
		{
			if(lg==begin)
				return 1;
			else
				if(s[begin+1]=='2')
					begin++;
				else
					if(s[begin+1]=='1'&&s[begin+3]=='3')
						begin+=4;
					else
						return 0;
			break;
		}
	case '3':
		{
			if(s[begin+1]=='2')
				begin++;
			else
				if(s[begin+1]=='1'&&s[begin+3]=='3')
					begin+=4;
				else
					return 0;
			break;
		}
	}
	return 1;
}
int main ()
{
	int n,lg,i,j;
	vector<char> v(Lmax);
	ifstream f("perle.in");
	ofstream g("perle.out");
	f>>n;
	for(i=1;i<=n;i++)
	{
		f>>lg;
		for(j=1;j<=lg;j++)
			f>>v[j];
		if(lg==1 )
			g<<'1'<<"\n";
		else
			if(lg==2)
				g<<'0'<<"\n";
			else
				if(check(v,lg))
					g<<'1'<<"\n";
				else
					g<<'0'<<"\n";
	}
	//map<char,pair<string,pair<string,string> > >abc;
	//abc['A'].first="1",abc['A'].second.first="2",abc['A'].second.second="3";
	return 0;
}