#include <iostream>
#include <fstream>
#include <string.h>
#include <conio.h>

using namespace std;
ifstream fin("perle.in");
ofstream fout("perle.out");
char sir[10001];
int verifC(char *);
int verifA(char *sir)
{
    if(strlen(sir)==1) return 1;
    return 0;
}
int verifB(char *sir)
{
    if(strlen(sir)==1)
        return 0;
    if(sir[0]=='3')
        return 0;
    if(sir[0]=='2')
        return verifB(sir+1);
    if(sir[0]=='1'&&sir[2]=='3'&&strlen(sir)>=5)
        return verifC(sir+4);
    return 0;
}
int verifBC(char *sir)
{
        
        char s1[10001];
        if(strlen(sir)>5)
            for(int i=1;i<strlen(sir)-1;i++)
            {
                strcpy(s1+1,sir);
                for(int j=0;j<i;j++)
                    s1[j]=s1[j+1];
                s1[i]=0;
                //cout<<s1<<" * "<<s1+i+1<<'\n';
              //  getch();
                if(verifB(s1)&&verifC(s1+i+1))
                    return 1;
            }
    return 0;
}
int verifC(char *sir)
{
    if(strlen(sir)==3&&sir[0]=='1'&&sir[1]=='2')
        return 1;
    if(strlen(sir)==1&&sir[0]=='2')
        return 1;
    if(sir[0]=='3')
        return verifBC(sir+1);
    return 0;
}
int main()
{
    int N,l,i,j;
    fin>>N;
    for(i=1;i<=N;i++)
    {
        fin>>l;
        for(j=0;j<l;j++)
            fin>>sir[j];
        sir[l]=0;
        if(verifA(sir)) fout<<"1"<<'\n';
        else
        if(verifB(sir)) fout<<"1"<<'\n';
        else
        if(verifC(sir)) fout<<"1"<<'\n';
        else fout<<'0'<<'\n';

    }
    return 0;
}