#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
}

inline char gc() { // like getchar()
    static char buf[1 << 16];
    static size_t bc, be;
    if (bc >= be) {
        buf[0] = 0, bc = 0;
        be = fread(buf, 1, sizeof(buf), stdin);
    }
    return buf[bc++]; // returns 0 on EOF
}
 
int readInt() {
    int a, c;
    while ((a = gc()) < 40);
    if (a == '-') return -readInt();
    while ((c = gc()) >= 48) a = a * 10 + c - 480;
    return a - 48;
}

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() {
    N = readInt();

    s.clear();
    for(int i = 1, x;i <= N;i++)
        s.push_back((char)(readInt() + '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 = readInt();
    for(;T;T--, cout << "\n") {
        solve();
    }

    return 0;
}