/*
A       1           2           3
B       2B          1A3AC
C       2           3BC         12A
*/
#include<stdio.h>
int a[20],answer;
int canbe(int seqStart,int seqLength);
int main(){
int i,j,k,m,n;
freopen("fin.txt","r",stdin);freopen("fout.txt","w",stdout);
scanf("%d\n",&n);
for(i=0;i<n;i++)            
    {                   
    scanf("%d",&m);
    for(j=1;j-1<m;j++)scanf("%d",&a[j]);
    printf("%d\n",canbe(1,m));
    }    
return 0;
}

int canbe(int seqStart,int seqLength)
    {
    if(seqLength==1 ||(seqLength==3&&a[seqStart]==1&&a[seqStart+1]==2))
        return 1;
    if(seqLength==2)
        return 0;        
    //looking after B1 shape
    if(a[seqStart]==2)
        return canbe(seqStart+1,seqLength-1);
    //looking after B2 shape
    if(seqLength>3&&a[seqStart]==1&&a[seqStart+2]==3&&(seqLength==5||seqLength==7||a[seqStart+4]==3))
        return canbe(seqStart+4,seqLength-4);
    //looking after C2 shape
    if(seqLength>6&&a[seqStart]==3&&a[seqStart]!=3)
        return canbe(seqStart+1,seqLength-1);
    return 0;
    }