#include <bits/stdc++.h>
using namespace std;
ifstream fin("perle.in");
ofstream fout("perle.out");
int n,m,i,j,v[10001],aux,cnt;
bool ok;
deque <char> sir;
bool number(char c){
    return 0 < c - '0' && c - '0' < 4;
}
int main()
{
    fin>>m;
    while(m--){
        fin>>n;
        for(i=1;i<=n;i++)
            fin>>v[i];
        if(n == 1)
            fout<<1<<'\n';
        else if(n == 2)
            fout<<0<<'\n';
        else if(n == 3 && v[1] == 1 && v[2] == 2)
            fout<<1<<'\n';
        else if(n == 5 && v[1] == 1 && v[3] == 3 && v[5] == 2)
            fout<<1<<'\n';
        else if(n > 5){
            if(v[1] == 3)
                sir.push_front('c');
            else
                sir.push_front('b');
            cnt = 1;
            ok = 1;
            while(!sir.empty() && !number(sir.front())){
                aux = sir.front();
                sir.pop_front();
                if(cnt > n){
                    ok = 0;
                    break;
                }
                if(aux == 'a'){
                    if(v[cnt] == 1) sir.push_front('1');
                    if(v[cnt] == 2) sir.push_front('2');
                    if(v[cnt] == 3) sir.push_front('3');
                }
                if(aux == 'b'){
                    if(v[cnt] == 1){
                        sir.push_front('c');
                        sir.push_front('a');
                        sir.push_front('3');
                        sir.push_front('a');
                        sir.push_front('1');
                    }else if(v[cnt] == 2){
                        sir.push_front('b');
                        sir.push_front('2');
                    }else{
                        ok = 0;
                        break;
                    }
                }
                if(aux == 'c'){
                    if(cnt < n && v[cnt] == 1 && v[cnt+1] == 2){
                        sir.push_front('a');
                        sir.push_front('2');
                        sir.push_front('1');
                    }else if(v[cnt] == 2){
                        sir.push_front('2');
                    }else if(v[cnt] == 3){
                        sir.push_front('c');
                        sir.push_front('b');
                        sir.push_front('3');
                    }else{
                        ok = 0;
                        break;
                    }
                }
                while(!sir.empty() && number(sir.front())){
                    if(v[cnt] == sir.front() - '0'){
                        cnt++;
                        sir.pop_front();
                    }else{
                        ok = 0;
                        break;
                    }
                }
            }
            if(cnt <= n || !sir.empty())
                ok = 0;
            fout<<ok<<'\n';
        }else
            fout<<0<<'\n';
    }
    return 0;
}