#include<fstream>
#define DIM 11005
using namespace std;
int t, n, i, x;
char s[DIM], v[DIM];
ifstream fin("perle.in");
ofstream fout("perle.out");
int solve(char c){
    int i, u = 1;
    s[1] = c;
    for(i = 1; i <= n; i++){
        if(u == 0){
            return 0;
        }
        if(s[u] >= '1' && s[u] <= '3'){
            if(s[u] == v[i]){
                u--;
            }
            else{
                return 0;
            }
            continue;
        }
        if(s[u] == 'a'){
            u--;
            continue;
        }
        if(s[u] == 'b'){
            if(v[i] == '3'){
                return 0;
            }
            if(v[i] == '1'){
                s[u] = 'c'; s[u + 1] = 'a'; s[u + 2] = '3'; s[u + 3] = 'a';
                u += 3;
            }
            continue;
        }
        if(v[i] == '2'){
            u--;
        }
        if(v[i] == '3'){
            s[u] = 'c'; s[u + 1] = 'b';
            u++;
        }
        if(v[i] == '1'){
            s[u] = 'a'; s[u + 1] = '2';
            u++;
        }
    }
    if(u == 0){
        return 1;
    }
    return 0;
}
int main(){
    fin>> t;
    for(; t; t--){
        fin>> n;
        for(i = 1; i <= n; i++){
            fin>> x;
            v[i] = x + '0';
        }
        if(solve('a')){
            fout<<"1\n";
            continue;
        }
        if(solve('b')){
            fout<<"1\n";
            continue;
        }
        if(solve('c')){
            fout<<"1\n";
            continue;
        }
        fout<<"0\n";
    }
    return 0;
}