#include <iostream>
#include <fstream>
using namespace std;
ifstream f("perle.in");
ofstream g("perle.out");

short n,i,j,li,x,poz;
bool ok;
char v[10105]="a",a[10005];

int main()
{
    f>>n;
    for(i=1; i<=n; i++)
    {
        f>>li;
        for(j=1; j<=li; j++)
            f>>v[j];
        v[li+1]=0;
        if(li==1)g<<1<<'\n';
        else if(li==2)g<<0<<'\n';
        else if(li==3)
        {
            if(v[1]=='1'&&v[2]=='2')g<<1<<'\n';
            else g<<0<<'\n';
        }
        else
        {
            ok=1;
            x=1;
            poz=1;
            if(v[1]=='3')a[1]='c';
                else a[1]='b';
            while(x!=0)
                if(a[x]=='b')
                {
                    if(v[poz]=='1' && v[poz+2]=='3')
                    {
                        a[x]='c';
                        poz=poz+4;
                    }
                    else if(v[poz]=='2')
                        poz++;
                    else
                    {
                        ok=0;
                        break;
                    }
                }
                else
                {
                    if(v[poz]=='2')
                    {
                         poz++;
                         x--;
                    }
                    else if(v[poz]=='1'&&v[poz+1]=='2')
                    {
                       poz+=3;
                       x--;
                    }
                    else if(v[poz]=='3')
                    {
                        x++;
                        a[x]='b';
                        poz++;
                    }
                    else
                    {
                        ok=0;
                        break;
                    }
                }
            g<<ok<<'\n';
        }
    }

}