#include <fstream>
using namespace std;
ifstream cin("perle.in");
ofstream cout("perle.out");
int n,st,dr;
bool pp;
char c[20005];
void B();
void C();
void B()
{
    st+=2;
    if(c[st]==2)
        B();
    else
    {
        if(c[st]=='1' && c[st+4]=='3')
        {
            st+=6;
            C();
        }
    }
}
void C()
{
    st+=2;

    if(c[st]=='2')
        st+=2;
    else
    {
        if(c[st]=='1')
        {
            if(c[st+2]=='2' && st+4==dr)
                st+=4;
        }
        else
        {
            B();
            C();
        }
    }
}
void rez()
{
    cin>>n;
    cin.get(c,2*n+1);
    if(n<=3)
    {
        if(n==1)
            cout<<"1\n";
        else
            if(n==2)
                cout<<"0\n";
            else
            {
               if(c[1]=='1' && c[3]=='2')
                    cout<<"1\n";
               else
                    cout<<"0\n";
            }
        return;
    }
    st=1;
    dr=n*2-1;
    pp=false;
    if(c[st]=='3')
        C();
    else
        B();
    if(st==dr)
        cout<<'1';
    else
        cout<<'0';
    cout<<'\n';
}
int main()
{
    int k;
    cin>>k;
    for(int j=0;j<k;j++)
        rez();
}