#include <bits/stdc++.h>
using namespace std;

ifstream in("perle.in");
ofstream out("perle.out");

stack<char> stiva;
int v[10001];

int main(){
int n,m;
string sir;
in >> n;

for(int i = 1; i <= n; i++){
    in >> m;
    sir = "";
    for(int j = 1; j <= m; j++){
        in >> v[j];}

    if(m == 1 || (m == 3 && v[1] == 1 && v[2] == 2)) out << "1" << "\n";

    else{
        int s = 1;
        bool ok = 1;
        if(v[1] == 1 && v[3] == 3 && m > 5){
            sir += "1";
            stiva.push('C');
            stiva.push('A');
            stiva.push('3');
            stiva.push('A');}

        if(v[1] == 2){
            sir += "2";
            stiva.push('B');}

        else if(v[1] == 3){
            sir += "3";
            stiva.push('C');
            stiva.push('B');}

        while(!stiva.empty()){
            int ch = stiva.top();
            stiva.pop();
            s++;
            if(ch == 'A' || (ch == 'C' && v[s] == 2) || (isdigit(ch) && ch - '0' == v[s])){
                sir += (v[s] + '0');}
            else if(ch == 'B' && v[s] == 2){
                sir += "2";
                stiva.push('B');}
            else if(ch == 'B' && v[s] == 1 && v[s + 2] == 3){
                sir += "1";
                stiva.push('C');
                stiva.push('A');
                stiva.push('3');
                stiva.push('A');}
            else if(ch == 'C' && v[s] == 3){
                sir += "3";
                stiva.push('C');
                stiva.push('B');}
            else if(ch == 'C' && v[s] == 1 && v[s + 1] == 2){
                sir += "12";
                s++;
                stiva.push('A');}}

            for(int i = 1; i <= m; i++){
                if(sir[i - 1] - '0' != v[i]){
                    ok = 0;
                    break;}}

            if(ok == 1 && sir.size() == m) out << "1" << "\n";
            else out << "0" << "\n";}}

return 0;
}