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

#include <fstream>
#include <vector>

#define in "perle.in"
#define out "perle.out"
#define Max_Size 10009

std :: ifstream f(in);
std :: ofstream g(out);

class Perle
{
    protected :
        int T, N, idx;
        std :: vector < int > V;

    public :
        bool C();
        bool B();
        bool Solve();
        void _main();

};

bool Perle :: C()
{
    if(V[idx] == 2 && idx < N) {
        ++idx;
        return 1;
    }

    if(V[idx] == 3)  {
        ++idx;
        if(B() && idx < N)  return C();
    }

    if(V[idx] == 1 && V[idx + 1] == 2 && idx + 2 < N)   {
        idx += 2;
        return 1;
    }

    return 0;
}

bool Perle :: B()
{
    if(V[idx] == 2) {
        ++idx;
        return B();
    }

    if(V[idx] == 1 && V[idx + 2] == 3 && idx + 4 < N)  {
        idx += 4;
        return C();
    }

    return 0;
}

bool Perle :: Solve()
{
    idx = 0;

    if(N == 1)  return 1;

    if(V[idx] == 2 || (V[idx] == 1 && V[idx + 2] == 3 && N >= 5))   return B();

    return C();
}

void Perle :: _main()
{
    f >> T;

    for(int i = 1; i <= T; ++i) {
        f >> N;
        V.clear();

        for(int x, j = 1; j <= N; ++j)    {
            f >> x;
            V.push_back(x);
        }

        int rez = Solve();

        g << rez << '\n';
    }
}

int main()
{
    Perle obj;

    obj._main();
}