#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) {

    for(int i = 0;i < (int)s.size();i++) {

        if(s[i] == '1')  {
            if(str[i] == 'A' || str[i] == '1') {
                str[i] = '1';
                continue;
            }

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

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

            return 0;
        }

        if(s[i] == '2') {
            if(str[i] == '2' || str[i] == 'A' || str[i] == 'C') {
                str[i] = '2';
                continue;
            }

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

            return 0;
        }

        if(s[i] == '3') {
            if(str[i] == 'A' || str[i] == '3') {
                str[i] = '3';
                continue;
            }

            if(str[i] == 'C')  {
                str.erase(i, 1);
                str.insert(i, "3BC");
                continue;
            }

            return 0;
        }

        if((int)str.size() > N)
            return 0;
    }

    return (str == s);
}

void solve() {
    N = readInt();

    s.clear();
    for(int i = 1;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;
}