#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 (str == s);

    if(s[i] == '1')  {
        if(str[i] == 'A' || str[i] == '1') {
            str[i] = '1';
            return _sol_(str, i + 1);
        }

        if(str[i] == 'B')  {
            str.erase(i, 1);
            str.insert(i, "1A3AC");
            return _sol_(str, i + 1);
        }

        if(str[i] == 'C') {
            str.erase(i, 1);
            str.insert(i, "12A");
            return _sol_(str, i + 1);
        }

        return 0;
    }

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

        if(str[i] == 'B') {
            str.erase(i, 1);
            str.insert(i, "2B");
            return _sol_(str, i + 1);
        }

        return 0;
    }

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

        if(str[i] == 'C')  {
            str.erase(i, 1);
            str.insert(i, "3BC");
            return _sol_(str, 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;
}