#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int perle[10002];

bool decodB(int p);
bool decodC(int p);

int n, p;

bool decodB(){
    if(p <= n - 1 && perle[p] == 2){
        p++;
        return decodB();
    }
    if(p <= n - 4 && perle[p] == 1){
        if(perle[p + 2] != 3)
            return 0;
        p += 4;
        return decodC();
    }
    return 0;
}

bool decodC(){
    if(p <= n - 2 && perle[p] == 3){
        if(decodB()){
            // p trebuie sa fie unde incepe C
            return decodC();
        }
        return 0;
    }
    if(p <= n - 2 && perle[p] == 1 && perle[p + 1] == 2){
         p += 3;
        return 1;
    }
    if(p <= n && perle[p] == 2){
         p++;
        return 1;
    }
    return 0;
}

int main()
{
    freopen("perle.in", "r", stdin);
    freopen("perle.out", "w", stdout);
    int t;
    scanf("%d", &t);
    for(int test = 1; test <= t; ++test){
        memset(perle, 0, sizeof(perle));
        scanf("%d ", &n);
        for(int i = 1; i <= n; ++i)
            scanf("%d ", &perle[i]);
        if(n == 1){
            printf("1\n");
            continue;
        }
        p = 1;
        if(decodB() && p - n == 1){
             printf("1\n");
            continue;
        }
        p = 1;
        if(decodC() && p - n == 1){
             printf("1\n");
              continue;
        }
        printf("0\n");
    }
    return 0;
}