/*
A -> 1 | 2 | 3
B -> 2B | 1A3AC
C -> 2 | 3BC | 12A
321
*/
#include <fstream>
using namespace std;
ifstream cin("perle.in");
ofstream cout("perle.out");
int n,i,j,k,v[1001];
int aux[1001];
bool ok;
void recurs(int a[], int poz)
{
    int i;
    if(!a[0])
        a[0]++;;
    for(i=poz; i<=a[0]; i++)
    {
        if((a[i]==1 || a[i]==2 || a[i]==3) && (v[j]!=a[j]))
            break;
        if(a[i]==4)
            a[i]=v[i];
        if(a[i]==5)
        {
            if(v[i]==2)
            {
                a[0]++;
                a[i]=2; a[i+1]=5;
                recurs(a,i);
            }
            if(v[i]==1)
            {
                a[0]+=4;
                a[i]=1; a[i+1]=4; a[i+2]=3; a[i+3]=4; a[i+4]=6;
                recurs(a,i);
            }
            break;
        }
        if(a[i]==6)
        {
            if(v[i]==2)
            {
                a[i]=2; recurs(a,i);
            }
            if(v[i]==3)
            {
                a[0]++;
                a[i]=2; a[i+1]=5;
                recurs(a,i);
            }
            if(v[i]==1 && v[i+1]==2)
            {
                a[0]+=2;
                a[i]=1; a[i+1]=2; a[i+2]=4;
                recurs(a,i);
            }
           break;
        }
    }
    if(a[0]==k && a[k]==v[k])
        ok=true;
}
int main()
{
    cin>>n;
    for(i=1; i<=n; i++)
    {
        cin>>k;
        for(j=1; j<=k; j++)
            cin>>v[j];
        //1 2 3 , A=4, B=5, C=6
        ok=false;
        if(k==1)
        {
            aux[1]=4; recurs(aux,1);
        }
        else
        {
            if(v[1]==2 || (v[1]==3 && v[2]==2) || v[1]==1)
            {
                 aux[1]=5; recurs(aux,1);
                 aux[1]=6; recurs(aux,1);
            }
        }
        if(ok==true)
            cout<<"1\n";
        else
            cout<<"0\n";
        for(j=0; j<=k; j++)
            aux[j]=0;
    }
}