#include <stdio.h>
#include <iostream>
#include <fstream>
#define NMAX 10000
using namespace std;
ifstream f("perle.in");
ofstream g("perle.out");
int st[2][NMAX + 10];
int main(void)
{
    int t, l, v, i;
    int niv[2];
    int valid[2];
    f >> t;
    while (t--)
    {
        f >> l;
        if (l == 1)
        {
            f >> l;
            g << 1 << endl;
        }
        else
        {
            valid[1] = valid[0] = 1;
            niv[1] = niv[0] = 1;
            st[0][0] = 5;
            st[1][0] = 6;
            while (l--)
            {
                f >> v;
                for (i = 0; i < 2; i++)
                {
                    if (valid[i])
                    {
                        if (st[i][niv[i] - 1] < 4)
                        {
                            if (st[i][--niv[i]] == v)
                                valid[i] = 1;
                            else
                                valid[i] = 0;
                            break;
                        }
                        if (st[i][niv[i] - 1] == 4)
                        {
                            niv[i]--;
                            break;
                        }
                        if (st[i][niv[i] - 1] == 5)
                        {
                            if (v == 3)
                                valid[i] = 0;
                            if (v == 1)
                            {
                                niv[i]--;
                                st[i][niv[i]++] = 6;
                                st[i][niv[i]++] = 4;
                                st[i][niv[i]++] = 3;
                                st[i][niv[i]++] = 4;
                            }
                            break;
                        }
                        if (v == 2) 
                            niv[i]--;
                        if (v == 1)
                        {
                            niv[i]--;
                            st[i][niv[i]++] = 4;
                            st[i][niv[i]++] = 2;
                        }
                        if (v == 3)
                        {
                            niv[i]--;
                            st[i][niv[i]++] = 6;
                            st[i][niv[i]++] = 5;
                        }
                    }
                    if (!niv[i] && l) 
                        valid[i] = 0;
                }
            }
            if ((niv[0] == 0 && valid[0] == 1) || (niv[1] == 0 && valid[1] == 1))
                g << 1 << endl;
            else
                g << 0 << endl;
        }
    }
    return 0;
}