#include<cstdio>
char v[110000],v2[110000];
void f()
    {int n,i,j,k;
    char a;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%c%c",&a,&v[i]);
    if(n==1)
        {printf("1\n");
        return ;
        }
    if(n==3)
        {if(v[1]=='1'&&v[2]=='2')
            printf("1\n");
        else
            printf("0\n");
        return ;
        }
    if(v[1]=='1'||v[1]=='2')
        v2[1]='B';
    else
        v2[1]='C';
    i=j=k=1;
    while(i<=n)
        {if(v2[j]=='B'&&v[i]=='2')
            if(i<=n-5)
                {i++;
                v2[j+1]='B';
                }
            else
                {printf("0\n");
                return ;
                }
        else
            if(v2[j]=='B'&&v[i]=='1')
                {if(i<=n-4)
                    if(v[i+2]!='3')
                        {printf("0\n");
                        return ;
                        }
                    else
                        {i+=4;
                        v2[j+1]='C';
                        }
                else
                    {printf("0\n");
                    return ;
                    }
                }
            else
                if(v2[j]=='C'&&v[i]=='1')
                    {if(v[i+1]=='2')
                        i+=3;
                    else
                        {printf("0\n");
                        return ;
                        }
                    if(i==n+1)
                        {printf("1\n");
                        return ;
                        }
                    }
                else
                    if(v2[j]=='C'&&v[i]=='2')
                        {i++;
                        if(i==n+1)
                            {printf("1\n");
                            return ;
                            }
                        }
                    else
                        if(v2[j]=='C'&&v[i]=='3')
                            {i++;
                            v2[j+1]='B';
                            v2[j+2]='C';
                            }
                        else
                            i++;
        j++;
        }
    printf("0\n");
    }
int main ()
{freopen ("perle.in","r",stdin);
freopen ("perle.out","w",stdout);
int t,i;
scanf("%d",&t);
for(i=1;i<=t;i++)
    f();
return 0;
}