#include <cstdio>
#include <stack>

using namespace std;

bool ok[2];
stack <int> s[2];

int main()
{
    int t,n,i,x;
    freopen("perle.in","r",stdin);
    freopen("perle.out","w",stdout);
    scanf("%d",&t);
    for (;t;--t)
    {
        scanf("%d",&n);
        if (n==1)
        {
            scanf("%d",&x);
            printf("1\n");
            continue;
        }
        ok[0]=1;
        ok[1]=1;
        s[0].push(5);
        s[1].push(6);
        for (;n;--n)
        {
            scanf("%d",&x);
            for(i=0;i<2;++i)
                if (ok[i])
                {
                    if (s[i].empty())
                        ok[i]=0;
                    else if (s[i].top()<4)
                    {
                        if (s[i].top()!=x)
                            ok[i]=0;
                        s[i].pop();
                    }
                    else if (s[i].top()==4)
                        s[i].pop();
                    else if (s[i].top()==5)
                    {
                        if (x==3)
                        {
                            ok[i]=0;
                            s[i].pop();
                        }
                        else if (x==1)
                        {
                            s[i].pop();
                            s[i].push(6);
                            s[i].push(4);
                            s[i].push(3);
                            s[i].push(4);
                        }
                    }
                    else
                    {
                        s[i].pop();
                        if (x==1)
                        {
                            s[i].push(4);
                            s[i].push(2);
                        }
                        else if (x==3)
                        {
                            s[i].push(6);
                            s[i].push(5);
                        }
                    }
                }
        }
        if ((ok[0]&&s[0].empty())||(ok[1]&&s[1].empty()))
            printf("1\n");
        else
            printf("0\n");
        while(!s[0].empty())
            s[0].pop();
        while(!s[1].empty())
            s[1].pop();
    }
    return 0;
}