#include<cstdio>
#include<stack>
#include<cstring>
int main()
{
    freopen("perle.in","r",stdin);
    freopen("perle.out","w",stdout);

    int t,n,a[10000+10],i;



    for(fscanf(stdin,"%d",&t);t;)
    {
        fscanf(stdin,"%d",&n);
        for(i=0;i<n;++i)
            fscanf(stdin,"%d",&a[i]);

        int *v=a;
        std::stack<char> st;

        if(n==1)
        {
            fputs("1\n",stdout);
            goto forloop;
        }
        if(n==3)
        {
            if(v[0]==1&&v[1]==2)
                fputs("1\n",stdout);
            else
                fputs("0\n",stdout);
            goto forloop;
        }

        if(*v==3)
            st.push('C');
        else
            st.push('B');
        while(!st.empty())
        {
            if(st.top()=='B')
            {
                st.pop();
                if(a+n-1-v>=0 && *v==2)
                    st.push('B'),++v;
                else if(a+n-1-v>=3 && *v==1 && *(v+2)==3)
                    st.push('C'),v+=4;
                else
                {
                    fputs("0\n",stdout);
                    goto forloop;
                }
            }
            else//'C'
            {
                st.pop();
                if(a+n-1-v>=0)
                {
                    if(*v==2)
                    {
                        ++v;
                        continue;
                    }
                    if(*v==3)
                    {
                        st.push('C');
                        st.push('B');
                        ++v;
                    }
                    else if(a+n-1-v>=2 && *v==1 && *(v+1)==2)
                        v+=3;
                    else
                    {
                        fputs("0\n",stdout);
                        goto forloop;
                    }

                }
                else
                {
                    fputs("0\n",stdout);
                    goto forloop;
                }
            }
        }
        if(a+n-1>v)
            fputs("0\n",stdout);
        else
            fputs("1\n",stdout);

        forloop:
        --t;
    }




    return 0;
}