#include <cstdio>
#include <algorithm>
#include <cstring>
#define Nmax 1000002
using namespace std;
int n, m, i, j, nr;
char s[Nmax], S[Nmax];
int ok(char s[])
{
    int n = strlen(s);
    char aux;
    if (n == 1)
        return 1;

    for (int i = 0; i < n; ++ i)
    {
        if (s[i] == '1' || s[i] == '2' || s[i] == '3')
        {
            aux = s[i];
            s[i] = 'A';
            if (ok(s))
                return 1;
            s[i] = aux;
        }
        if (s[i] == '2' && s[i + 1] == 'B' && i + 1 < n)
        {
            strncpy(S, s, i);
            s[i] = 'B';
            strcat(S, s + i + 2);
            if (ok(S))
                return 1;
            else memset(S, 0, sizeof(S));
        }
        if (s[i] == '1' && s[i + 1] == 'A' && s[i + 2] == '3' && s[i + 3] == 'A' && s[i + 4] == 'C' && i + 4 < n)
        {
            strncpy(S, s, i);
            S[i] = 'B';
            strcat(S, s + i + 5);
            if (ok(S))
                return 1;
            else memset(S, 0, sizeof(S));
        }
        if (s[i] == '3' && s[i + 1] == 'B' && s[i + 2] == 'C' && i + 2 < n)
        {
            strncpy(S, s, i);
            S[i] = 'C';
            strcat(S, s + i + 3);
            if (ok(S))
                return 1;
            else memset(S, 0, sizeof(S));
        }
        if (s[i] == '2')
        {
            s[i] = 'C';
            if (ok(s))
                return 1;
            s[i] = '2';
        }
        if (s[i] == '1' && s[i + 1] == '2' && s[i + 2] == 'A' && i + 2 < n)
        {
            strncpy(S, s, i);
            S[i] = 'C';
            strcat(S, s + i + 3);
            if (ok(S))
                return 1;
            else memset(S, 0, sizeof(S));
        }
    }
    return 0;
}
int main()
{
    freopen("perle.in", "r", stdin);
    freopen("perle.out", "w", stdout);
    scanf("%d\n", &n);
    while (n --)
    {
        scanf("%d ", &m);
        memset(s, 0, sizeof(s));
        for (i = 1; i <= m; ++ i)
        {
            scanf("%d", &nr);
            s[i - 1] = nr + '0';
        }
        printf("%d\n", ok(s));
    }
    return 0;
}