#include <fstream>
#include <math.h>
#include <algorithm>

using namespace std;
#define llu long long unsigned
#define pb push_back
#define mp make_pair

string problemName = "perle";
string inFile = problemName+".in";
string outFile = problemName+".out";
ifstream fin(inFile.c_str());
ofstream fout(outFile.c_str());

//common pearl: 1 - 1
//              2 - 2
//              3 - 3
//magic pearl : A - 0
//              B - -1
//              C - -2
//nothing - 4

int v[10005];
int s[10020];
char h[3][4][6];
int n;

void prep(){
    h[0][0][0] = '3';//A have 3 transformations
    h[0][1][0] = '1';
    h[0][1][1] = '1';
    h[0][2][0] = '1';
    h[0][2][1] = '2';
    h[0][3][0] = '1';
    h[0][3][1] = '3';

    h[1][0][0] = '2';//B have 2 transformations
    h[1][1][0] = '2';
    h[1][1][1] = '2';
    h[1][1][2] = 'B';
    h[1][2][0] = '5';
    h[1][2][1] = '1';
    h[1][2][2] = 'A';
    h[1][2][3] = '3';
    h[1][2][4] = 'A';
    h[1][2][5] = 'C';

    h[2][0][0] = '3';//C have 3 transformations
    h[2][1][0] = '1';
    h[2][1][1] = '2';
    h[2][2][0] = '3';
    h[2][2][1] = '3';
    h[2][2][2] = 'B';
    h[2][2][3] = 'C';
    h[2][3][0] = '3';
    h[2][3][1] = '1';
    h[2][3][2] = '2';
    h[2][3][3] = 'A';
}

bool bkt(int k, int c){
    if(c == n+1 && k == n){
        return true;
    }else if(k > n+1){
        return false;
    }
    int i,j,l,ll,limit,x;
    bool ok = false;
    if(c == 1){
        for(i = 0;i < 3;i++){
            for(j = 1;j <= h[i][0][0]-'0';j++){
                if(h[i][j][1]-'0' == v[c]){
                    limit = h[i][j][0]-'0';
                    for(ll = 1;ll < limit;ll++){
                        s[c+ll+limit] = s[c+ll];
                    }
                    x = s[c];
                    for(ll = 1, l = c;ll <= limit;ll++, l++){
                        if(h[i][j][ll] >= '1' && h[i][j][ll] <= '3'){
                            s[l] = h[i][j][ll]-'0';
                        }else{
                            s[l] = -(h[i][j][ll]-'A');
                        }
                    }
                    ok |= bkt(k+limit-1, c+1);
                    if(ok == true){
                        return ok;
                    }
                    for(ll = 1;ll < limit;ll++){
                        s[c+ll] = s[c+ll+limit];
                        s[c+ll+limit] = 5;
                    }
                    s[c] = x;
                }
            }
        }
    }else if(s[c] >= 1 && s[c] <= 3){
        if(s[c] != v[c]){
            return false;
        }
        ok |= bkt(k, c+1);
        if(ok == true){
            return ok;
        }
    }else if(s[c] >= -2 && s[c] <= 0){
        i = -s[c];
        for(j = 1;j <= h[i][0][0]-'0';j++){
            if(h[i][j][1]-'0' == v[c]){
                limit = h[i][j][0]-'0';
                for(ll = 1;ll < limit;ll++){
                    s[c+ll+limit] = s[c+ll];
                }
                x = s[c];
                for(ll = 1, l = c;ll <= limit;ll++, l++){
                    if(h[i][j][ll] >= '1' && h[i][j][ll] <= '3'){
                        s[l] = h[i][j][ll]-'0';
                    }else{
                        s[l] = -(h[i][j][ll]-'A');
                    }
                }
                ok |= bkt(k+limit-1, c+1);
                if(ok == true){
                    return ok;
                }
                for(ll = 1;ll < limit;ll++){
                    s[c+ll] = s[c+ll+limit];
                    s[c+ll+limit] = 5;
                }
                s[c] = x;
            }
        }
    }
    return false;
}

int main(){
    prep();
    int T,test,i,j,k;
//    for(i = 0;i < 3;i++){
//        char ch = i+'A';
//        fout<<"Vecinii lui "<<ch<<" sunt : ";
//        for(j = 1;j <= h[i][0][0]-'0';j++){
//            for(k = 1;k <= h[i][j][0]-'0';k++){
//                fout<<h[i][j][k];
//            }
//            fout<<' ';
//        }
//        fout<<'\n';
//    }
    fin>>T;
    for(test = 1;test <= T;test++){
        fin>>n;
        for(i = 1;i <= n;i++){
            fin>>v[i];
            s[i] = 5;
        }
        fout<<bkt(1, 1)<<'\n';
    }
    return 0;
}