#include <cstdio>
#include<cctype>
#include <stack>
#define BM 10005
using namespace std;
int sc[BM];
stack < char > sa;
stack<char>af;
int n,dim,vf;
int main (){
	int l,i,j,ok;
	freopen("perle.in","r",stdin);
	freopen("perle.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;++i){
		scanf("%d",&l);
		dim=0;
		vf=0;
		ok=1;
		for(j=1;j<=l;++j)scanf("%d",&sc[j]);
		if(l==1)printf("1\n");
		else {
			for(j=1;j<=l;++j){
				//fprintf(stderr,"%d ",j);
				if(sc[j]==2){
					if(sa.size()==0){
						if(j==1)sa.push('B');
						if(j!=1){
							printf("0\n");
							ok=0;
							break;
						}
					}
					else {
						if(sa.top()=='A')sa.pop();
						else if(sa.top()=='C'){
							if(j!=l){
								printf("0\n");
								ok=0;
								break;
							}
							else sa.pop();
						}
						else {
							if(isdigit(sa.top())){
								if(sa.top()-'0'!=sc[j]){
									printf("0\n");
									ok=0;
									break;
								}
								else sa.pop();
							}
						}
					}
				}
				else if(sc[j]==3){
					if(sa.size()==0){
						if(j==1)sa.push('C');
						else {
							printf("0\n");
							ok=0;
							break;
						}
					}
					else {
						if(sa.top()=='A')sa.pop();
						else if(sa.top()=='B'){
							printf("0\n");
							ok=0;
							break;
						}
						else if(sa.top()=='C'){
							sa.pop();
							sa.push('C');
							sa.push('B');
						}
						else if(isdigit(sa.top())){
							if(sa.top()-'0'!=sc[j]){
								printf("0\n");
								ok=0;
								break;
							}
							else sa.pop();
						}
					}
				}
				else if(sc[j]==1){
					if(sa.size()==0){
						if(j==1){
							if(l==3){
								sa.pop();
								sa.push('A');
								sa.push('2');
							}
							else if(l>3){
								sa.pop();
								sa.push('C');
								sa.push('A');
								sa.push('3');
								sa.push('A');
							}
							else if(l<3){
								printf("0\n");
								ok=0;
								break;
							}
						}
						else {
							printf("0\n");
							ok=0;
							break;
						}
					}
					else if(sa.top()=='A')sa.pop();
					else if(sa.top()=='B'){
						sa.pop();
						sa.push('C');
						sa.push('A');
						sa.push('3');
						sa.push('A');
					}
					else if(sa.top()=='C'){
						sa.pop();
						sa.push('A');
						sa.push('2');
					}
					else if(isdigit(sa.top())){
						if(sa.top()-'0'!=sc[j]){
							printf("0\n");
							ok=0;
							break;
						}
						else sa.pop();
					}
				}
				/*for(;sa.size();sa.pop()){
					fprintf(stderr,"%c",sa.top());
					af.push(sa.top());
				}
				fprintf(stderr,"\n");
				for(;af.size();af.pop())sa.push(af.top());*/
			}
			if(ok==1&&sa.size()==0)printf("1\n");
			if(ok==1&&sa.size()>0)printf("0\n");
			
		}
	}
	return 0;
}