#include <bits/stdc++.h>
using namespace std;
ifstream f("perle.in");
ofstream g("perle.out");
char s_3bc(int*v,int n);
char trysolve(int*,int,char);
char s_3bc(int *v,int n){
      v=v+1;
        n--;
    int nrb=1;
    int nrc=1;
    while(v[0]==2&&n>0)
        v=v+1,n--;
    if(n==0)
        return '0';
    if(v[0]==1&&n>=5&&v[2]==3)
    {
        nrc=2;
        nrb=0;
        v=v+4;
        n=n-4;
    }
    else
        return '0';
    if(n>=3&&v[n-3]==1&&v[n-2]==2)
        {nrc--;
        n=n-3;
        v=v+3;
        }
    else
        if(n>=1&&v[n-1]==2)
        {
        nrc--;
        n=n-1;
        v=v+1;
        }
    if(nrc==2)
        return '0';
    return trysolve(v,n,'C');
}
char trysolve(int *v,int n,char caz=' '){
    if(n==0)
        return '0';
    if(caz=='B'){
        while(v[0]=='2'&&n>0){
            v=v+1;
            n--;
        }
        if(v[0]==1&&n>=5&&v[2]==3)
            return trysolve(v+4,n-4,'C');
        return '0';
    }
    if(caz=='C'){
        if(v[0]==2)
            return (n=1)? '1':'0';
        if(v[0]==1)
            if(v[1]==2&&n==3)
                return '1';
            else
                return '0';

        return s_3bc(v,n);
    }
}
char solve()
{
    int v[10005],l;
    f>>l;
    for(int i=0;i<l;i++)
        f>>v[i];
    if(l==1)
        return '1';
    int nr=0;
    while(v[nr]==2&&nr<l)
        nr++;
     if(nr!=0)
        return trysolve(v+nr,l-nr,'B');
    if(v[0]==1&&v[1]==1&&l==3)
        return '1';
    if(v[0]==3)
        return trysolve(v,l,'C');
    else
        return trysolve(v,l,'B');

}
int main()
{
    int n;
    f>>n;
    for(int i=0;i<n;i++)
        g<<solve()<<"\n";
    return 0;
}