#include <bits/stdc++.h>
using namespace std;

ifstream in("perle.in");
ofstream out("perle.out");

#define cin in
#define cout out

int n,a[10005],poz;
bool ok=1;

void tb();
void tc();

void tc() 
{
    if(a[poz]==2 and ok) poz++;
    else if(ok and a[poz]==1 and a[poz+1]==2 and poz+2<=a[0])
        ((ok and (a[poz+2]==1 or a[poz+2]==2 or a[poz+2]==3)) ? poz+=3: ok=0);
    else if(ok and a[poz]==3 and poz<a[0])
    {
        poz++;
        tb();
        if(poz<=a[0])
        {
            if(ok) tc();
        }
        else
            ok=0;
    }
    else
        ok=0;
    
}

void tb() 
{
    if(a[poz]==2 and ok and poz<a[0]) poz++,tb();
    else if(a[poz]==1 and ok and poz<=a[0])
    {
        if(ok and poz+1<=a[0] and (a[poz+1]==1 or a[poz+1]==2 or a[poz+1]==3))
        {
            if(ok and a[poz+2]==3 and poz+2<=a[0])
            {
                if(ok and poz+3<=a[0] and (a[poz+3]==1 or a[poz+3]==2 or a[poz+3]==3))
                    poz+=4,tc();
                else
                    ok=0;
            }
            else
                ok=0;
        }
        else
            ok=0;
    }
    else
        ok=0;
}

int main()
{
    cin>>n;
    
    while(n--)
    {
        cin>>a[0];
        
        for(int i=1;i<=a[0];i++)
            cin>>a[i];
          
        poz=1;
        ok=1;
        
        if(a[poz]==1)
        {
            if(a[0]<=3)
            {
                if(a[0]==3)
                {
                    if(a[poz+1]==2)
                    {
                        if(a[poz+2]==1 or a[poz+2]==2 or a[poz+2]==3)cout<<1<<'\n';
                        else cout<<0<<'\n';
                    }
                    else cout<<0<<'\n';
                }
                else if(a[0]==1) cout<<1<<'\n';
                else cout<<0<<'\n';
            }
            else
            {
                tb();
                if(poz>a[0]) cout<<1<<'\n';
                else cout<<0<<'\n';
            }
        }
        else if(a[poz]==2)
        {
            if(a[0]==1) cout<<1<<'\n';
            else
            {
                tb();
                if(poz>a[0]) cout<<1<<'\n';
                else cout<<0<<'\n';
            }
        }
        else if(a[poz]==3)
        {
            if(a[0]==1) cout<<1<<'\n';
            else
            {
                tc(); 
                if(poz>a[0]) cout<<1<<'\n';
                else cout<<0<<'\n';
            }
        }
        else cout<<0<<'\n';    
    }
    return 0;
}