#include <bits/stdc++.h>

using namespace std;
ifstream fin ("perle.in");
ofstream fout ("perle.out");

    int n,dim,j,ok;
    char c[10005],ch;

void B();
void C();

void Citire()
{
    int k=-1;
    fin >> ch;
    dim=ch-'0';
    for(int i=1;i<=dim;i++)
    {
    fin >>ch;
    if(isdigit(ch))c[++k]=ch;
    }
}

void Clean()
{
    for(int i=strlen(c)-1;i>=0;i--)c[i]=NULL;
}

void B(bool da)
{
    if(da==1)j++;
    while(c[j]=='2')j++;
    if(c[j]=='1'&&c[j+2]=='3')
    {
     if(j+4>=strlen(c))ok=0;
     else
        {
        j+=3;
        C();
        }
    }
}
void C()
{
    j++;
    if(c[j]=='2'&&j==strlen(c)-1)ok=1;
    else if(c[j]=='1'&&c[j+1]=='2'&&(strlen(c)-1==j+2))ok=1;
    else if(c[j]=='3')B(1);
}

int main()
{
    fin >> n;
    fin.get();
    for(int i=1;i<=n;++i)
    {
    Citire();
    j=0;ok=2;
    if(dim==1)fout <<1 <<'\n';
    else if(dim==2)fout <<0 <<'\n';
    else while(j<dim&&ok==2)
    {
    if(c[j]=='2'||c[j]=='3')B(1);
    else B(0);
    C();
    }
    if(ok!=2)fout <<ok <<'\n';
    Clean();
    }

    return 0;
}