#include <fstream>

using namespace std;

ifstream fin ("perle.in");
ofstream fout ("perle.out");
int l = 1, v[10001], n, x;
char c[10003];

int a(), b(), cc();

int verif(){
    for(int i = 1; i <= n; i++){
        if(v[i] != c[i] - '0'){
            return 0;
        }
    }
    return 1;
}

int a(){
    c[l] = v[l] + '0';
    return 0;
}

int cc(){
    if(v[l] == 1 && v[l + 1] == 2){
        c[l] = '1';
        c[++l] = '2';
        c[++l] = 'A';
        a();
    }
    if(l >= n){
        return 0;
    }
    if(v[l] == 2){
        c[l] = '2';
    }
    if(l >= n){
        return 0;
    }
    if(v[l] == 3){
        c[l] = '3';
        c[++l] = 'B';
        b();
        c[++l] = 'C';
        cc();
    }
    if(l >= n){
        return 0;
    }
    return 0;
}

int b(){
    if(v[l] == 1){
        c[l] = '1';
        c[++l] = 'A';
        a();
        c[++l] = '3';
        c[++l] = 'A';
        a();
        c[++l] = 'C';
        cc();
    }
    if(l >= n){
        return 0;
    }
    if(v[l] == 2){
        c[l] = '2';
        c[++l] = 'B';
        b();
    }
    return 0;
}

int main()
{
    fin>>x;
    for(int k = 1; k <= x; k++){
        fin>>n;
        for(int i = 1; i <= n; i++){
            fin>>v[i];
        }
        c[1] = 'B';
        l = 1;
       for(int i = 1; c[i] != 0; i++){
            c[i] = ' ';
       }
        if(b() == 0){
            if(verif() == 0){
                c[1] = 'C';
                l = 1;
                for(int i = 1; c[i] != 0; i++){
            c[i] = ' ';
       }
                if(cc() == 0){
                    if(verif() == 0){
                        c[1] = 'A';
                        l = 1;
                        for(int i = 1; c[i] != 0; i++){
            c[i] = ' ';
       }
                        if(a() == 0){
                            if(verif() == 0){
                                fout<<0<<"\n";
                            }
                            else{
                                fout<<1<<"\n";
                            }
                        }
                    }
                    else{
                        fout<<1<<"\n";
                    }
                }

            }
            else{
                fout<<1<<"\n";
            }
        }
    }
    return 0;
}