#include <fstream>
using namespace std;

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

int sir[10001] , indice;

bool Evaluare_C();

bool Evaluare_B ()
{
    if (indice > sir[0])
        { indice++; return false; }

    if (sir[indice] == 2)
        { indice++; return Evaluare_B(); }

    if (indice + 4 <= sir[0] && sir[indice] == 1 && sir[indice + 2] == 3)
        { indice += 4 ; return Evaluare_C(); }

    return false;
}

bool Evaluare_C ()
{
    if (indice > sir[0])
        { indice++; return false; }

    if (sir[indice] == 1)
    {
        if (sir[indice + 1] == 2)
            { indice += 3; return true; }

        return false;
    }

    if (sir[indice] == 2)
        { indice++; return true; }

    indice++; return Evaluare_B() ? Evaluare_C() : false;
}

int main ()
{
    int teste;
    cin >> teste;

    for (int test = 1 ; test <= teste ; test++)
    {
        cin >> sir[0];
        for (int indice = 1 ; indice <= sir[0] ; indice++)
            cin >> sir[indice];

        indice = 2;
        if (indice == sir[0] + 1) cout << "1\n";
        else {
            indice = 1; Evaluare_B();
            if (indice == sir[0] + 1) cout << "1\n";
            else {
                indice = 1; Evaluare_C();
                if (indice == sir[0] + 1) cout << "1\n";
                else cout << "0\n";
            }
        }
    }

    cout.close(); cin.close();
    return 0;
}