#include <fstream>
using namespace std;
ifstream f("perle.in");
ofstream g("perle.out");
int n,p,m;
char s[10002];

void Transform_B();
void Transform_C();

int main()
{
    int i;
    f>>n;
    for(i=1; i<=n; i++)
    {
        f>>m;
        f.get();
        f.getline(s,10001);
        p=0;
        Transform_C();
        if(p==m)
            g<<1<<'\n';

        else
            g<<0<<'\n';
    }
    return 0;
}

void Transform_B()
{
    if(m-p>=5)
    {
        if(s[p]=='1')
        {
            p+=4;
            Transform_C();
        }
        else
        {
            p++;
            Transform_B();
        }
    }
}

void Transform_C()
{
    if(m-p==1)
        p++;
    else if(s[p]=='3')
    {
        p++;
        Transform_B();
        Transform_C();
    }
    else if(s[p]=='2')
        Transform_B();
    else if(s[p]=='1')
    {
        p++;
        if(s[p]=='2')
            p+=2;
        else
            Transform_B();
    }
}