#include<fstream>
#include<string.h>
using namespace std;
int main()
{
    fstream f("perle.in", ios::in), g("perle.out", ios::out);
    int i,j,n,l;
    char v1[10000];
    f>>n;
    for(i=0;i<n;i++)
    {
        f>>l;
        for(j=0;j<l;j++)
        {
            f>>v1[j];
        }
        if(l==2||l==4)
        {
            g<<0<<"\n";
        }
        else
             if(l==3)
                if(v1[0]=='1'&&v1[1]=='2')
                {
                    g<<1<<"\n";
                }
                 else  g<<0<<"\n";
             else
                if(l==5)
                    if(v1[0]=='1'&&v1[2]=='3'&&v1[4]=='2')
                     g<<1<<"\n";
                    else
                         g<<0<<"\n";
                else
                if(l==6)
                    if(v1[0]=='0'&&v1[1]=='1'&&v1[3]=='3'&&v1[5]=='2')
                {
                     g<<1<<"\n";
                }
                else     g<<0<<"\n";
                else
                if(l==7)
                    if(v1[0]!='1')
                    g<<0<<"\n";
                else  g<<1<<"\n";
                else
                    g<<1<<"\n";
    }

    return 0;
}