#include <stdio.h>
#define Max 10001
#define FOR(i, a, b) for (i = (a); i <= (b); i++)
 
int T, L, N;
int a[Max], pos;
char q[Max];
char perla;
 
int process()
{
 
    while (N)
    {
    perla = q[N]; N--;
 
    if (pos > L) return 0;
 
    if (perla == 'B')
    {
        if (a[pos] == 1)
        {
        if (pos + 4 > L) return 0;
        if (a[pos + 2] == 3)
            q[++N] = 'C', pos += 4;
        else             return 0;
        }
        else if (a[pos] == 2)
        q[++N] = 'B', pos += 1;
        else                 return 0;
    }
    if (perla == 'C')
    {
        if (a[pos] == 2) pos++;
        else if (a[pos] == 3) q[++N] = 'C', q[++N] = 'B', pos += 1;
        else if (a[pos] == 1)
        {
        if (pos + 2 > L) return 0;
        if (a[pos + 1] == 2)
            pos += 3;
        else             return 0;
        }
    }
    }
    if (pos > L) return 1;
    return 0;
}
                 
int main()
{
    int i, j;
    FILE *fin = fopen("perle.in", "rt");
    FILE *fout = fopen("perle.out", "wt");
    fscanf(fin, "%d", &T);
    for (i = 1; i <= T; i++)
    {
        fscanf(fin, "%d", &L);
    for (j = 1; j <= L; j++) fscanf(fin, "%d", &a[j]);
    if (L == 1) fprintf(fout, "1\n");
    if (L == 1) continue;
 
    N = 1; q[N] = 'B'; pos = 1;
    int x1 = process();
 
    N = 1; q[N] = 'C'; pos = 1;
    int x2 = process();
 
    if (x1 || x2) fprintf(fout, "1\n");
    else          fprintf(fout, "0\n");
    }
    fclose(fin);
    fclose(fout);
 
    return 0;
}