#include <bits/stdc++.h>
using namespace std;
ifstream in("perle.in");
ofstream out("perle.out");
stack<char> q;
int v[10005];
char a='a';
char b='b';
char c='c';
int main()
{
    int tst,n,x;
    in>>tst;
    while(tst--)
    {
        in>>n;
        for(int i=1;i<=n;++i)
            in>>v[i];
        while(!q.empty()) q.pop();
        if(n==1)
        {
            out<<1<<'\n';
            continue;
        }
        if(n==3 and v[1]==1 and v[2]==2)
        {
            out<<1<<'\n';
            continue;
        }
        if(v[1]==1)
            q.push(b);
        else if(v[1]==2)
            q.push(b);
        else if(v[1]==3)
            q.push(c);
        int ind=1;
        while(!q.empty() and ind<=n)
        {
            char x=q.top(); q.pop();
            if(x==a)
                ++ind;
            else if(x==b)
            {
                if(v[ind]==1)
                {
                    ind+=2;
                    if(ind>n or v[ind]!=3)
                    {
                        q.push(a);
                        break;
                    }
                    ind+=2;
                    q.push(c);
                }
                else if(v[ind]==2)
                {
                    ++ind;
                    q.push(b);
                }
                else if(v[ind]==3)
                {
                    q.push(a);
                    break;
                }
            }
            else if(x==c)
            {
                if(v[ind]==1)
                {
                    ++ind;
                    if(ind>n or v[ind]!=2)
                    {
                        q.push(a);
                        break;
                    }
                    ++ind;
                    q.push(a);
                }
                else if(v[ind]==2)
                    ++ind;
                else if(v[ind]==3)
                {
                    ++ind;
                    q.push(c);
                    q.push(b);
                }
            }
        }
        if(q.empty() and ind>n) out<<1<<'\n';
        else out<<0<<'\n';
    }
    return 0;
}