#include <iostream>
#include <fstream>
#include <stack>
using namespace std;
ifstream f("perle.in");
ofstream g("perle.out");
stack<int> stiva;
///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')
            {
                stiva.push(3);
                indice++;
            }
            else
            {
                stiva.push(2);
                indice++;
            }
            ok=1;
            inStiva=1;
            while(!stiva.empty()&&ok==1&&indice<=test[0]-48)
            {
                element=stiva.top();
                stiva.pop();
                /*if(i==1)
                    cout<<element<<' '<<inStiva<<' '<<sfStiva<<' '<<indice<<'\n';*/
                if(element==2)
                {
                    if(test[indice]=='2')
                    {
                        indice++;
                        stiva.push(2);
                    }
                    else if(test[indice]=='1'&&test[indice+2]=='3')
                    {
                        indice+=4;
                        stiva.push(3);
                    }
                    else ok=0;
                }
                else if(element==3)
                {
                    if(test[indice]=='2')
                        indice++;
                    else if(test[indice]=='3')
                    {
                        stiva.push(2);
                        stiva.push(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||!stiva.empty())
                    {
                        ok=0;
                        /*if(i==1)
                            cout<<inStiva<<' '<<sfStiva<<' '<<indice<<' '<<test[0]-48;*/
                    }
                g<<ok<<'\n';
        }
    }

}