#include <bits/stdc++.h>

using namespace std;

inline void Open(const string Name) {
    #ifndef ONLINE_JUDGE
        (void)!freopen((Name + ".in").c_str(), "r", stdin);
        (void)!freopen((Name + ".out").c_str(), "w", stdout);
    #endif
}

string s;

int N;

int _sol_(string str, int i) {
    if(i > N)
        return 0;

    if(i == N) 
        return (str == s);

    if(s[i] == '1')  {
        if(str[i] == 'A' || str[i] == '1') 
            return _sol_(str.substr(0, i) + "1" + str.substr(i + 1), i + 1);

        if(str[i] == 'B') 
            return _sol_(str.substr(0, i) + "1A3AC" + str.substr(i + 1), i + 1);

        if(str[i] == 'C') 
            return _sol_(str.substr(0, i) + "12A" + str.substr(i + 1), i + 1);

        return 0;
    }

    if(s[i] == '2') {
        if(str[i] == '2' || str[i] == 'A' || str[i] == 'C') 
            return _sol_(str.substr(0, i) + "2" + str.substr(i + 1), i + 1);

        if(str[i] == 'B') 
            return _sol_(str.substr(0, i) + "2B" + str.substr(i + 1), i + 1);

        return 0;
    }

    if(s[i] == '3') {
        if(str[i] == 'A' || str[i] == '3') 
            return _sol_(str.substr(0, i) + "3" + str.substr(i + 1), i + 1);

        if(str[i] == 'C') 
            return _sol_(str.substr(0, i) + "3BC" + str.substr(i + 1), i + 1);

        return 0;
    }

    return 0;
}

void solve() {
    cin >> N;

    s.clear();
    for(int i = 1, x;i <= N;i++)
        cin >> x, s.push_back((char)(x + '0'));

    if(N == 1) {
        cout << 1;
        return;
    }

    cout << (_sol_("B", 0) || _sol_("C", 0));
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    Open("perle");

    int T; cin >> T; 
    for(;T;T--, cout << "\n") {
        solve();
    }

    return 0;
}