#include<cstdio>
#define MAX 10000
using namespace std;

int v[MAX+1];
char st[MAX+1];
int k;

int main(){
    freopen ("perle.in","r",stdin);
    freopen ("perle.out","w",stdout);
    int n,t,i,fl,ce;

    scanf ("%d",&t);

    for(;t>0;t--){
        scanf ("%d",&n);
        for(i=1;i<=n;i++)
            scanf ("%d",&v[i]);

        fl=2;

        if (n==1) fl=1;
        else
        if (v[1]==3){
            if (n>=3){
                st[0]='c';
                st[1]='b';
                k=2;
            }
            else fl=0;
        }
        else
        if (v[1]==2){
            st[0]='b';
            k=1;
        }
        else
        if (n==3 &&(v[2]==2 ||v[3]==3)) fl=1;
        else {
            st[0]='c';
            st[1]='a';
            st[2]=3;
            st[3]='a';
            k=4;
        }

        i=2;
        while(fl==2 &&i<=n &&k>0){
            ce=st[k-1];
            k--;

            if (ce<=3){
                if (ce!=v[i]) fl=0;
            }
            else
            if (ce=='c'){
                if (v[i]==1){
                    st[k]='a';
                    st[k+1]=2;
                    k+=2;
                }
                else
                if (v[i]==3){
                    st[k]='c';
                    st[k+1]='b';
                    k+=2;
                }
            }
            else
            if (ce=='b'){
                if (v[i]==3) fl=0;
                else
                if (v[i]==2) k++;
                else {
                    st[k]='c';
                    st[k+1]='a';
                    st[k+2]=3;
                    st[k+3]='a';
                    k+=4;
                }
            }

            i++;
        }

        if (fl==2){
            if (i==n+1 &&k==0) fl=1;
            else fl=0;
        }

        printf ("%d\n",fl);
    }

    return 0;
}