#include<fstream>
using namespace std;

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

int v1[10000],n,v2[10000],i1,i2,i3,i,r,z,n2;
const int a=4,b=5,c=6;

int main()
{
	f>>n;
	for (i1=1;i1<=n;i1++){
		f>>n2;
		for (i2=1;i2<=n2;i2++)
			f>>v1[i2];
		if (n2==1){
			g<<"1"<<endl;
			z=1;
		}
		else {
			v2[0]=b;
			for (i3=1;i3<=n2;i3++){
				if (v1[0]==7)
					v1[0]=8;
				if (v2[0]==b) {
					if (v1[i3]==2){
						v2[i3]=2;
						i3=i3+1;
						v2[0]=5;
					}
					if (v1[i3]==1) {
						v2[i3]=1;
						i3=i3+1;
						v2[i3]=4;
						i3=i3+1;
						v2[i3]=3;
						i3=i3+1;
						v2[i3]=4;
						i3=i3+1;
						v2[i3]=6;
						v2[0]=6;
					}
				}
				if (v2[0]==c) {
					if ((v1[i3]==2)&&(n2!=i3)) {
						g<<"0"<<endl;
						z=1;
						break;
					}
					if ((v1[i3]==1)&&(v1[i3+1]==2)&&(n2==i3+2)){
						g<<"1"<<endl;
						z=1;
						break;
					}
					if (v1[i3]==3) {
						v2[i3]=3;
						i3=i3+1;
						v2[i3]=5;
						i3=i3+1;
						v2[i3]=6;
						v2[0]=5;
						i3=i3-1;
						v1[0]=7;
					}
				}
				if (v1[0]==8) {
					i3=i3+1;
					if (v2[0]==c) {
						if ((v1[i3]==2)&&(n2!=i3)) {
							g<<"0"<<endl;
							z=1;
							break;
						}
						if ((v1[i3]==1)&&(v1[i3+1]==2)&&(n2==i3+2)){
							g<<"1"<<endl;
							z=1;
							break;
						}
						if (v1[i3]==3) {
							v2[i3]=3;
							i3=i3+1;
							v2[i3]=5;
							i3=i3+1;
							v2[i3]=6;
							v2[0]=5;
							i3=i3-1;
							v1[0]=7;
						}
					}
				}
			}
		}
		if (z!=1)
			for (i=1;i<=n2;i++)
				if ((v2[i]!=v2[i])&&(v2[i]!=4)){
					g<<"0"<<endl;
					r=1;
					break;
				}
		if (r==0)
			g<<"1"<<endl;
	}
	return 0;
}