#include <bits/stdc++.h>

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

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

void B();
void C();

void Citire()
{
    int i;
    fin.getline(c,25005);
    dim=0;
    for(i=0;c[i]!=' ';i++)
        dim=dim*10+c[i]-'0';
    for(;c[i];i++)
        if(c[i]==' ')strcpy(c+i,c+i+1);
}

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();
    ///fout <<dim <<" " << c << '\n';
    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;
}