#include <fstream>
using namespace std;

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

int v1[1000],v2[1500],n,n2,n3,j,x;
int i1,i2,i3,i4,i5,i,r;
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++){
			v2[i2]=0;
			f>>v1[i2];
		}
		x=1;
		v2[0]=0;
		v1[0]=0;
		for (i3=b;i3<=c;i3++){
			if (n2==1)
				if ((v1[1]==1||v1[1]==2||v1[1]==3)&&n2==1){
					g<<"1"<<endl;
					r=1;
					break;
				}
			else
				x=1;
				if (i3==b)
					v2[0]=5;
				else
					v2[0]=6;
				for (x=1;x<=n2;x++){
					if (v2[0]==b) {
						if (v1[x]==2){
							v2[x]=2;
							x=x+1;
							v2[x]=5;
							v2[0]=5;
						}
						else {
							if (v1[x]==1){
								v2[x]=1;
								x=x+1;
								v2[x]=4;
								x=x+1;
								v2[x]=3;
								x=x+1;
								v2[x]=4;
								x=x+1;
								v2[x]=6;
								v2[0]=6;
							}
						}
					}
					else 
						if (v2[0]==c) {
							if (v1[x]==2){
								v2[x]=2;
								if (x!=n2){
									
									break;
								}
								else {
									break;
								}
							}
							else {
								if (v1[x]==1){
									if (n2==x+2){
										v2[x]=1;
										x=x+1;
										v2[x]=2;
										x=x+1;
										v2[x]=4;
									}
									else 
										break;
								}
								else{
									v2[x]=3;
									x=x+1;
									v2[0]=5;
									v1[0]=6;
								}
							}
						}
				}
		}
		x=0;
		for (i=1;i<=n2;i++){
			x=x+1;
			if (v1[i]!=v2[x]&&v2[x]!=4){
				i5=1;
				break;
			}
		}
		g<<endl;
		if (r==0)
			if (i5==0)
				g<<"1"<<endl;
			else 
				g<<"0"<<endl;
	}
	return 0;
}