#include <cstdio>
using namespace std;

int t, n;
int a[10005];
inline bool check(int p, int L, char c, int nr){
    if(L <= nr) return 0;
    if(L == 1 && c == 'B') return 0;
    if(L == 1 && c == 'C' && a[p] != 2) return 0;
    if(L == 1) return 1;
    if(c == 'A') {
        if(nr == 0) return 0;
        check(p + 1, L - 1, 'C', nr - 1);
    }
    if(c == 'C'){
        if(a[p] == 1){
            ++p;
            if(a[p] != 2) return 0;
            return check(p + 1, L - 2, 'A', nr);
        }
        else if(a[p] == 3) return check(p + 1, L - 1, 'B', nr + 1);
        else if(a[p] == 2){
            if(nr == 0) return 0;
            return check(p + 1, L - 1, 'C', nr - 1);
        }
    }
    if(c == 'B'){
        if(a[p] == 2){
            return check(p + 1, L - 1, 'B', nr);
        }
        if(a[p] == 1){
            p += 2;
            if(a[p] != 3) return 0;
            p += 2;
            return check(p, L - 4, 'C', nr);
        }
    }
    return 0;

}
int main()
{
    freopen("perle.in", "r", stdin);
    freopen("perle.out", "w", stdout);
    scanf("%d", &t);
    while(t--){
        scanf("%d", &n);
        for(int i = 1; i <= n ; ++i)
            scanf("%d", &a[i]);
        char c = 'A';
        if(n > 1){
            if(a[1] == 2) c = 'B';
            else if(a[1] == 1 && n == 3) c = 'C';
            else if(a[1] == 1) c = 'B';
            else if(a[1] == 3) c = 'C';
        }
        printf("%d\n", check(1, n, c, 0));
    }
    return 0;
}