#include <bits/stdc++.h>
using namespace std;
ifstream f("perle.in");
ofstream g("perle.out");
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';
    while(nrc&&n)
    {
        if(v[0]==2&&n>0)
            {nrc--;
            v=v+1;
            n--;
            }
        if(v[0]==1&&v[1]==2&&n>=3)
            {
            nrc--;
            v=v+3;
            n=n-3;
            }
    }
    if(n==0&&nrc=0)
        return '1';

}
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,l,'C');
    else
        return trysolve(v+nr,l-nr,'B');
}
int main()
{
    int n;
    f>>n;
    for(int i=0;i<n;i++)
        g<<solve()<<"\n";
    return 0;
}