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

using namespace std;
ifstream fin("perle.in");
ofstream fout("perle.out");
char sir[10001];
int k=1;
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)
{
    if(sir[strlen(sir)-1]=='2')
    {
        sir[strlen(sir)-1]=0;
        return verifB(sir);
    }
    if(sir[strlen(sir)-3]=='1'&&sir[strlen(sir)-2]=='2')
    {
        sir[strlen(sir)-3]=0;
        return verifB(sir);
    }
    return 0;
}
int verifC(char *sir)
{
    if(strlen(sir)==1&&sir[0]=='2')
        return 1;
    if(strlen(sir)==3&&sir[0]=='1'&&sir[1]=='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;
}