#include <iostream>
#include <fstream>
using namespace std;
ifstream f("perle.in");
ofstream g("perle.out");
int stiva[10010];
///A=1, B=2, C=3
int n;
char x[10010],test[10010];
int main()
{
    int i,j,inStiva=0,sfStiva=0,indice,element;
    bool ok;
    f>>n;
    for(i=1; i<=n; i++)
    {
        f>>test[0];
        ok=0;
        for(j=1; j<=test[0]-48; j++)
            f>>test[j];
        if(test[0]=='1')
            g<<'1'<<'\n';
        else if(test[0]=='3'&&test[1]=='1'&&test[2]=='1')
            g<<'1'<<'\n';
        else if(test[0]=='3')
            g<<'0'<<'\n';
        else
        {
            indice=1;
            if(test[1]=='3')
            {
                sfStiva++;
                stiva[1]=3;
                indice++;
            }
            else
            {
                sfStiva++;
                stiva[1]=2;
                indice++;
            }
            ok=1;
            inStiva=0;
            while(inStiva<=sfStiva&&ok==1&&indice<=test[0]-48)
            {
                inStiva++;
                element=stiva[inStiva];
                /*if(i==1)
                    cout<<element<<' '<<inStiva<<' '<<sfStiva<<' '<<indice<<'\n';*/
                if(element==2)
                {
                    if(test[indice]=='2')
                    {
                        indice++;
                        sfStiva++;
                        stiva[sfStiva]=2;
                    }
                    else if(test[indice]=='1'&&test[indice+2]=='3')
                    {
                        indice+=4;
                        sfStiva++;
                        stiva[sfStiva]=3;
                    }
                    else ok=0;
                }
                else if(element==3)
                {
                    if(test[indice]=='2')
                        indice++;
                    else if(test[indice]=='3')
                    {
                        sfStiva++;
                        stiva[sfStiva]='2';
                        sfStiva++;
                        stiva[sfStiva]='3';
                        indice++;
                    }
                    else if(test[indice]=='1'&&test[indice+1]=='2')
                    {
                        indice+=3;
                    }
                    else ok=0;
                }
            }
                int lungime;
                lungime=test[0]-48;
                if(indice<lungime||inStiva<sfStiva)
                    {
                        ok=0;
                        /*if(i==1)
                            cout<<inStiva<<' '<<sfStiva<<' '<<indice<<' '<<test[0]-48;*/
                    }
                g<<ok<<'\n';
        }
    }

}