#include<iostream.h>
#include<fstream.h>
int main()
{int T,Li,x,t,r,k;
long p,j;
fstream f("perle.in",ios::in),g("perle.out",ios::out);
f>>T;
for (t=0;t<T;t++)
{f>>Li;
p=0;
j=1;
for (r=0;r<Li;r++)
{f>>x;
p=p+x*j;
j=j*10;
}
if (p<10)
	g<<1<<endl;
if ((p>10)&&((p%10)!=2))
	g<<0<<endl;
	else
{k=p%10;
while (k==2)
	{p=p/10;
	k=p%10;
	if (p==0)
		{k=3;
		g<<0<<endl;
	}
	}
}
if (p!=0)
	{if (((p%10==1)&&(((p/100)%10)==3)&&(((p/10000)%10)==2)&&(p/100000==0))||((p%10==1)&&(((p/100)%10)==3)&&((p/10000)%10==1)&&((p/100000)%10==2)&&(p/1000000!=0)))
		g<<1<<endl;
}
}
}