#include<fstream>
using namespace std;
#define INF 0x3f3f3f3f
ifstream fin("perle.in");
ofstream fout("perle.out");
int t,n,L[10005];
int isB(int poz);
int isC(int poz);
int main()
{
    int ii,i;
    fin>>t;
    for (ii=0;ii<t;++ii)
    {
        fin>>n;
        for (i=1;i<=n;++i)
            fin>>L[i];
        if (n==1)
        {
            fout<<"1\n";
            continue;
        }
        if (n==2)
        {
            fout<<"0\n";
            continue;
        }
        if (L[1]==2)
        {
            if (isB(1)==n)
                fout<<"1\n";
            else
                fout<<"0\n";
        }
        else
        {
            if (L[1]==1)
            {
                if (n==3 && L[2]==2)
                    fout<<"1\n";
                else
                {
                    if (isB(1)==n)
                        fout<<"1\n";
                    else
                        fout<<"0\n";
                }
            }
            else
            {
                if (isC(1)==n)
                    fout<<"1\n";
                else
                    fout<<"0\n";
            }
        }
    }
    return 0;
}
int isB(int poz)
{
    if (poz>n) return INF;
    if (L[poz]==3) return INF;
    if (L[poz]==2)
        return isB(poz+1);
    return isC(poz+4);
}
int isC(int poz)
{
    if (poz>n) return INF;
    if (L[poz]==2) return poz;
    if (L[poz]==1 && L[poz+1]==2) return poz+2;
    int pos=isB(poz+1);
    return isC(pos+1);
}