#include <fstream>
#include <vector>
using namespace std;
const char iname[] = "perle.in";
const char oname[] = "perle.out";
int T, N, step;
vector < int > V;
bool B();
bool C();
bool A()
{if(N == 1)  return 1;
if(V[step] == 2 || (V[step] == 1 && V[step + 2] == 3 && N >= 5)) return B();
return C();
}bool B()
{
// B -> 2B | 1A3AC
if(V[step] == 2)    {++step;
if(step <= N)   return B();
    }
if(V[step] == 1 && V[step + 2] == 3 && step + 4 <= N)   {
step += 4;
return C();
}
return 0;
}
bool C()
{
// C -> 2 | 3BC | 12A

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

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

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

    return 0;
}

int main()
{
    ifstream f(iname);  ofstream g(oname);

    f >> T;

    for(int t = 1; t <= T; ++t) {
        f >> N;
        V.push_back(-1);

        for(int i = 1, x; i <= N; ++i)  {
            f >> x;
V.push_back(x);
}step = 1;
g << A() << '\n';
V.clear();
}g.close();
return 0;
}