#include <fstream>
#include <stack>

using namespace std;

ifstream cin("perle.in");
ofstream cout("perle.out");

stack<char> st;
char cuv[10001];
int n,ln;

int main(void)
{
    cin>>n;
    for(int o=1;o<=n;o++)
    {
        cin>>ln;
        char aux;
        for(int i=1,j=0;j<ln;i++)
            {
                cin>>aux;
                if(aux!=' ')
                    cuv[j++]=aux;
            }
        cuv[ln]='\0';
        if(ln==1)
            cout<<"1\n";
        else if(ln==3)
        {
            if(cuv[0]=='1' and cuv[1]=='2')
                cout<<"1\n";
            else
                cout<<"0\n";
        }
        else
        {
            bool obtinut=true;
            if(cuv[0]=='3')
                st.push('C');
            else if(cuv[0]!='3') st.push('B');
            int k=0;
            int executii=0;
            int aux_k=k;
            while(k!=ln)
            {
                char perla_extrasa=st.top();
                //cout<<perla_extrasa<<" ";
                st.pop();
                if(perla_extrasa=='B')
                {
                    if(cuv[k]=='2')
                        k++,aux_k++,st.push('B');
                    else if(cuv[k]=='1' and cuv[k+2]=='3')
                        k+=4,aux_k++,st.push('C');
                    else 
                    {
                        obtinut=false;
                        break;
                    }
                }
                else if(perla_extrasa=='C')
                {
                    if(cuv[k]=='2')
                        k++,aux_k++;
                    else if(cuv[k]=='3')
                        st.push('C'),st.push('B'),k++,aux_k++;
                    else if(cuv[k]=='1' and cuv[k+1]=='2')
                        k+=3,aux_k++;
                    else
                    {
                        obtinut=false;
                        break;
                    }
                }
            }
            cout<<obtinut<<"\n";
        }
    }
}