#include <iostream>
#include <fstream>
#define N_MAX 10005

using namespace std;

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

int test;
int n, arr[N_MAX];
int index;

bool A();
bool B();
bool C();

bool A(){
    if (index > n)
        return false;

    if (arr[index] == 1 || arr[index] == 2 || arr[index] == 3){
        index++;
        return true;
    }
    return false;
}

bool B(){
    if (index > n)
        return false;

    if (arr[index] == 2){
        index++;
        return B();
    }
    else if (arr[index] == 1){
        index++;
        if (A() == false)
            return false;
        if (arr[index] != 3)
            return false;
        index++;
        if (A() == false)
            return false;
        return C();
    }
    else
        return false;
}

bool C(){
    if (index > n)
        return false;

    if (arr[index] == 2 && index == n){
        index++;
        return true;
    }
    else if (arr[index] == 3){
        index++;
        if (B() == false)
            return false;
        return C();
    }
    else if (index <= n-2 && arr[index] == 1 && arr[index+1] == 2){
        index += 2;
        return A();
    }
    else
        return false;
}

int main()
{
    bool flag;

    in >> test;
    for (int i=1; i<=test; ++i){
        in >> n;
        for (int j=1; j<=n; ++j)
            in >> arr[j];

        index = 1;
        flag = false;

        if (A() && index == n + 1)
            flag = true;
        index = 1;
        if (B() && index == n + 1)
            flag = true;
        index = 1;
        if (C() && index == n + 1)
            flag = true;

        out << flag << '\n';
    }

    return 0;
}