#include<stdio.h>
char a[11000];
int p=1;
int fa();
int fb();
int fc();
int main()
{
    freopen("perle.in","r",stdin);
    freopen("perle.out","w",stdout);
    int n,i,u,j;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&u);
        for(j=1;j<=u;j++)
            scanf(" %c",&a[j]);
        if((fc() || fb() || fa())&&p>=u)
            printf("1\n");
        else
            printf("0\n");
    }
    return 0;
}
int fa()
{
    if(a[p]=='1' || a[p]=='2' || a[p]=='3')
    {
        p++;
        return 1;
    }
    return 0;
}
int fb()
{
    if(a[p]==2)
    {
        p++;
        if(fb())
            return 1;
    }
    if(a[p]==1 && a[p+2]==3)
    {
        p+=4;
        return fc();
    }
    return 0;
}
int fc()
{
    if(a[p]==2)
    {
        p++;
        return 1;
    }
    if(a[p]==3)
    {
        p++;
        if(fb())
            return fc();
    }
    if(a[p]==1 && a[p+1]==2)
        return fa();
    return 0;
}