#include <fstream>

using namespace std;
ifstream cin("perle.in");
ofstream cout("perle.out");
const int mxN = 1e4 + 10;
int v[mxN+1], i, n;
bool  A(), B(), C();
void solve()
{
    cin >> n;
    for(int i = 1;i<=n;i++)
        cin >> v[i];

    i = 1;
    bool rez = A();
    if(rez && i == n + 1)
    {
        cout << "1\n";
        return;
    }

    i = 1;
    rez = B();
    if(rez && i == n + 1)
    {
        cout << "1\n";
        return;
    }

    i = 1;
    rez = C();
    if(rez && i == n + 1)
    {
        cout << "1\n";
        return;
    }

    cout << "0\n";
    return;


}
int main()
{
    int t; cin >> t;
    while(t--)
        solve();
    return 0;
}
bool A() /// A -> {1, 2 , 3}
{
    if(i == n + 1)
        return false;
    if(v[i] == 1 || v[i] == 2 || v[i] == 3)
    {
        i++;
        return true;
    }
    return false;
}
bool B() /// B -> { 2B , 1A3AC }
{
    if(i == n + 1)
        return false;
    if(v[i] == 2) /// 2B
    {
        i++;
        return B();
    }
    if(v[i] == 1) /// 1A3AC
    {
        i++;
        bool aux = A();
        if(!aux) return false;
        if(v[i] != 3) return false;
        i++;
        aux = A();
        if(!aux) return false;
        return C();
    }
    return false;
}

bool C() /// C -> { 2 , 3BC , 12A }
{
    if(i == n + 1)
        return true;
    if(v[i] == 2) // 2
    {
        i++;
        return true;
    }
    if(v[i] == 3) // 3BC
    {
        i++;
        int aux = B();
        if(!aux) return false;
        return C();
    }
    if(v[i] == 1) // 12A
    {
        i++;
        if(v[i] != 2)
            return false;
        i++;
        return A();
    }

}