#include<fstream>

using namespace std;

ifstream f("perle.in");
ofstream g("perle.out");

char s[20000],c;
int n,ind,i,nn,iii;

bool A();
bool B();
bool C();

bool A()
{
	if(s[ind++]>='0'&&s[ind]<='9')
		return true;
	ind--;
	return false;
}

bool B()
{
	if(s[ind++]=='2'&&B())
		return true;
	ind--;
	if(s[ind++]=='1'&&A()&&s[ind++]=='3'&&A()&&C())
		return true;
	ind-=2;
	return false;
}

bool C()
{
	if(s[ind++]=='2')
		return true;
	ind--;
	if(s[ind++]=='3'&&B()&&C())
		return true;
	ind--;
	if(s[ind++]=='1'&&s[ind++]=='2'&&A())
		return true;
	ind-=2;
	return false;
}

int main()
{
	f>>n;f.get();
	for(int ii=1;ii<=n;ii++)
	{
		f>>nn;f.get();
		for(iii=0;iii<nn;iii++)
		{
			f.get(s[iii]);f.get();
		}
		s[iii]=0;
		ind=0;
		if(strlen(s)==1)
			g<<1<<endl;
		else
			if(s[0]=='3')
			{
				if(C())
					g<<1<<endl;
				else g<<0<<endl;
			}
			else
				if(s[0]=='2')
				{
					if(B())
						g<<1<<endl;
					else g<<0<<endl;
				}
				else
					if(s[0]=='1')
					{
						if(B()&&C())
							g<<1<<endl;
						else
							g<<0<<endl;
					}
					else
						g<<0<<endl;
	}
	f.close();
	g.close();
	return 0;
}