#include <iostream>
#include <fstream>
#define MAX_N 10011
using namespace std;
char v[MAX_N];
int n;
int b(int i);   int c(int i);

int main()
{
    int t,x,rez;
    ifstream fin("perle.in");
    ofstream fout("perle.out");
    fin>>t;
    while (t--)
    {
    	fin>>n;
    	for (int i=1;i<=n;++i)
    		fin>>v[i];
        if (n==1)
        	fout<<1<<'\n';
        else
        {
        	rez=b(1);
        	if(rez!=n+1)
                rez=c(1);
            if(rez==n+1)
                fout<<1<<'\n';
            else
                fout<<0<<'\n';
        }
    }
    fin.close();
    fout.close();

    return 0;
}

int b(int i)
{
    if(i>n+1)
        return n+2;
    if(v[i]=='2')
        return b(i+1);
    if(v[i]=='1'&&v[i+2]=='3')
        return c(i+4);
    return n+2;
}

int c(int i)
{
    if(v[i]=='2')
        return i+1;

    if(v[i]=='1'&&v[i+1]=='2')
        return i+3;
    if(v[i]=='3')
        return c(b(i+1));
    return n+2;
}