#include <bits/stdc++.h>

using namespace std;

#define NMAX 10005
#define cin fin
#define cout fout

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

map<string,int> dp;
string ans;
int n,x,a[NMAX],sz,rez;

bool verif(string aux) {
    if (dp[aux] == -1)
        return 0;
    else if (dp[aux] == 1)
        return 1;
    int lit = 0;
    int len = aux.size();
    int poz = 0;
    for (int i=0; i < len; i++) {
        if (aux[i] == 'A' || aux[i] == 'B' || aux[i] == 'C') {
            lit++;
            poz = i;
            break;
        }
    }
    if (!lit && len < sz) return 0;
    if (len > sz) {dp[aux]=-1; return 0;}
    if (!lit && len == sz) {
        if (aux == ans)
        {
            dp[aux] = 1;
            return 1;
        }
        else
        {
            dp[aux] = -1;
            return 0;
        }
    }
    else if (lit) {
            bool ok = 0;
            if (aux[poz] == 'A') {
                aux[poz] = '1';
                if (verif(aux) == 1) {dp[aux] = 1; ok=1; return 1;}
                else {
                    dp[aux] = -1;
                    aux[poz] = '2';
                    if (verif(aux) == 1) {dp[aux] = 1; ok=1; return 1;}
                    else {
                        dp[aux] = -1;
                        aux[poz] = '3';
                        if (verif(aux) == 1) {dp[aux] = 1; ok = 1; return 1;}
                        else
                            dp[aux] = -1;
                    }
                }
                if (!ok) {dp[aux] = -1; return 0;}
            }
            else if (aux[poz] == 'B') {
                string st = aux.substr(0,poz);
                string dr = "2B" + aux.substr(poz+1);
                if (verif(st+dr) == 1) {
                    ok = 1;
                    dp[st+dr] = 1;
                    return 1;
                }
                else {
                    dp[st+dr] = -1;
                    string st = aux.substr(0,poz);
                    string dr = "1A3AC" + aux.substr(poz+1);
                    if (verif(st+dr) == 1) {
                        ok = 1;
                        dp[st+dr] = 1;
                        return 1;
                    }
                    else {
                        dp[st+dr] = -1;
                    }
                }
                if (!ok) {
                    dp[aux] = -1;
                    return 0;
                }
            }
            else if (aux[poz] == 'C') {
                aux[poz] = '2';
                if (verif(aux) == 1) {ok = 1; return 1;}
                else {
                    dp[aux] = -1;
                    string st = aux.substr(0,poz);
                    string dr = "3BC" + aux.substr(poz+1);
                    if (verif(st+dr) == 1) {dp[st+dr] = 1; ok=1; return 1;}
                    else {
                        dp[st+dr] = -1;
                        string dr = "12A" + aux.substr(poz+1);
                        if (verif(st+dr) == 1) {dp[st+dr] = 1; ok = 1; return 1;}
                        else
                            dp[st+dr] = -1;
                    }
                }
                if (!ok) {
                    dp[aux] = -1;
                    return 0;
                }
        }
    }
}

int main()
{
    cin >> n;
    cin.get();
    while (n--) {
        dp.clear();
        rez = 0;
        ans = "";
        cin >> x;
        sz = x;
        for (int i=1; i <= x; i++)
            cin >> a[i] , ans += a[i]+'0';
        if (verif("A"))
            cout << 1 << '\n';
        else if (verif("B"))
            cout << 1 << '\n';
        else if (verif("C"))
            cout << 1 << '\n';
        else
            cout << 0 << '\n';
    }
    return 0;
}