/*
A -> 1  | 2     | 3
B -> 2B | 1A3AC
C -> 2  | 3BC   | 12A
*/

#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

int main()
{
    ifstream f("perle.in");
    ofstream g("perle.out");
    char stiva[20], perla;
    int sir[10001], p=0, n, i, dim, dimstiva, j;
    f>>n;
    for(j=1; j<=n; j++)
    {
        f>>dim;
        for(i=0; i<dim; i++)
            f>>sir[i];
        if(dim==1)
            g<<"1"<<"\n";
        else if(dim==3)
        {
            if(sir[0]==1 && sir[1]==2)
                g<<"1"<<"\n";
            else
                g<<"0"<<"\n";
        }
        else
        {
            p=0;
            dimstiva=-1;
            bool ok=true;
            if(sir[0]==3)
                stiva[++dimstiva]='C';
            else
                stiva[++dimstiva]='B';
            while(p!=dim)
            {
                perla=stiva[dimstiva];
                dimstiva--;
                if(perla=='B')
                {
                    if(sir[p]==2)
                    {
                        p++;
                        stiva[++dimstiva]='B';
                    }
                    else if(sir[p]==1 && sir[p+2]==3)
                    {
                        p=p+4;
                        stiva[++dimstiva]='C';
                    }
                    else
                    {
                        ok=false;
                        break;
                    }
                }
                else if(perla=='C')
                {
                    if(sir[p]==2)
                    {
                        p++;
                    }
                    else if(sir[p]==3)
                    {
                        stiva[++dimstiva]='C';
                        stiva[++dimstiva]='B';
                        p++;
                    }
                    else if(sir[p]==1 && sir[p+1]==2)
                        p=p+3;
                    else
                    {
                        ok=false;
                        break;
                    }
                }
            }
            g<<ok<<"\n";
        }
    }
    return 0;
}