#include <fstream>

using namespace std;
ofstream g("perle.out");
int l,j;
char v[100010];
int rec(int &i,char a)
{
    if(a=='A')
        if(i==l)
            return 1;
        else
            return 2;
    else
        if(a=='B')
        {
            if(v[i]=='2')
            {
                i+=1;
                return rec(i,a);
            }
            else
                if(v[i]=='3')
                {
                    i+=1;
                    int b,c;
                    b=rec(i,a);
                    if(b==2)
                    {
                        i+=1;
                        a='C';
                        return rec(i,a);
                    }
                    else
                        return 0;
                }
                else
                    if(v[i]=='1')
                    {
                        if(v[i+1]=='2' and i+2==l)
                            return 1;
                        else
                        {
                            if(v[i+2]=='3')
                                if(i+4<=l)
                                {
                                    i=i+4;
                                    return rec(i,'C');
                                }
                                else
                                    return 0;
                        }
                    }
        }
        else
        {
            if(v[i]=='2' and i==l)
                return 1;
            else
                if(v[i]=='1' and v[i+1]=='2' and i+2==l)
                    return 1;
                else
                    if(v[i]=='3')
                    {
                        i+=1;
                        int b;
                        b=rec(i,'B');
                        if(b==2)
                        {
                            i+=1;
                            if(rec(i,'C')==1)
                                return 1;
                            else
                                return 0;
                        }
                        else
                            return 0;
                    }
        }
}
int main()
{
    ifstream f("perle.in");
    int n,i,j,c;
    f>>n;
    for(i=1;i<=n;i++)
    {
        f>>l;
        f.get();
        j=1;
        for(j=1;j<=l;j++)
        {
            f>>v[j];
            f.get();
        }

        if(l==1)
            g<<"1";
        else
            if(l==2)
                g<<"0";
            else
                {
                    j=1;
                    if(v[j]=='2')
                    {
                        j=2;
                        c=rec(j,'B');
                        if(c==1)
                            g<<"1";
                        else
                            g<<"0";
                    }
                    else
                        if(v[1]=='1' and v[2]=='2' and l==3)
                            g<<"1";
                        else
                            if(v[1]=='1')
                                g<<"0";
                            else
                                if(v[1]=='3')
                            {
                                j=2;
                                c=rec(j,'B');
                                if(c==2)
                                {
                                    j+=1;
                                    c=rec(j,'C');
                                    if(c==1)
                                        g<<"1";
                                    else
                                        g<<"0";
                                }
                            }

                }
        g<<'\n';

    }
    return 0;
}