#include<stdio.h>


const int maxn = 100000;


int m;
int a[maxn];
int st[maxn];
int j;
int i;
int l;
int n;

int bkt()
{
        if (m==1) return 1;
        if (m==3&&a[1]==1&&a[2]==2) return 1;
        i=1;
        l=0;
        if (a[1]==2)
        {
                l=1;
                st[l]=2;
                i++;
        }
        if (a[1]==1&&a[1+2]==3)
        {
                l=1;
                st[l]=3;
                i+=4;
        }
        if (a[1]==3)
        {
                l++;
                st[l]=2;
                l++;
                st[l]=3;
                i++;
        }
        j=1;
        while (1)
        {
                if (a[i]==1)
                {
                        if (st[j]==2&&a[i+2]==3)
                        {
                                l++;
                                st[l]=3;
                                j++;
                                i+=4;
                        }
                        if (st[j]==3&&a[i+1]==2&&i+2==m) return 1;
                }

                if (a[i]==2)
                {
                        if (st[j]==2)
                        {
                                i++;
                        }
                        if (st[j]==3&&i==m&&j==l) return 1;
                        
                }
                if (a[i]==3)
                {
                        if (st[j]==2)  return 0;
                        if (st[j]==3)
                        {
                                i++;
                                j--;
                                st[j]=2;
                        }
                }
                if (i>m && l>=j) return 0;
        }
        return 0;
}


int main()
{
        freopen("perle.in","r",stdin);
        freopen("perle.out","w",stdout);
        scanf("%d",&n);
        int i1;
        for(i1=1;i1<=n;i1++)
        {
                scanf("%d",&m);
                for(j=1;j<=m;j++)
                        scanf("%d",&a[j]);
                printf("%d\n",bkt());
        }
        return 0;


}