#include<fstream>
using namespace std;
ifstream fin("perle.in");
ofstream fout("perle.out");
int n,i,d,j;
char sir[10005];
int v[10005];
int perle(int x)
{
    if(i>n) return 1;
    else
    {
        if(x==1)
        {
            if(n!=1) return 0;
            i++;
        }
        if(x==2)
        {
            if(v[i]==3) return 0;
            if(v[i]==2)
            {
                if(i==n) return 0;
                i++;
                perle(2);
            }
            if(v[i]==1)
            {
                if(n-4<i) return 0;
                if(v[i+2]!=3) return 0;
                i=i+4;
                perle(3);
            }
        }
        if(x==3)
        {
            if(v[i]==2)
            {
                if(i==n) i++,perle(1);
                else return 0;
            }
            if(v[i]==3)
            {
                i++;
                perle(2);
                i++;
                perle(3);
            }
            if(v[i]==1)
            {
                if(v[i+1]!=2 or n-i!=2) return 0;
                i=n+1;
                perle(1);
            }
        }
    }
}
int main()
{
    fin>>d;
    for(j=1;j<=d;j++)
    {
        fin>>n;
        fin.get(sir,10005);
        i=1;
        for(int dd=1;dd<=n;dd++)
        {
            v[dd]=sir[i]-'0';
            i+=2;
        }
        i=2;
        int rez=0;
        if(n==1) rez=perle(1);
        if(v[1]==2) rez=perle(2);
        if(v[1]==3) rez=perle(3);
        if(v[1]==1 and n>1) rez=perle(3);
        fout<<rez<<'\n';
    }
    return 0;
}