#include<cstdio>
#include<deque>
using namespace std;
int t,n,i,x;
deque<char> A,B;
int main()
{
    freopen("perle.in","r",stdin);
    freopen("perle.out","w",stdout);
    scanf("%d",&t);
    for(;t;t--)
    {
        scanf("%d",&n);
        A.resize(0);
        B.resize(0);
        for(i=1;i<=n;i++)
        {
            scanf("%d",&x);
            A.push_back(x+'0');
        }
        if(n==1)
        {
            printf("1\n");
            continue;
        }
        if(A.front()=='1')
        {
            if(n<3) B.push_back('A');
            else if(n<5) B.push_back('C');
            else B.push_back('B');
        }
        else if(A.front()=='2') B.push_back('B');
        else B.push_back('C');
        while(A.size()&&B.size())
        {
            if(A.front()==B.front())
            {
                A.pop_front();
                B.pop_front();
                continue;
            }
            //
            if(B.front()=='A')
            {
                A.pop_front();
                B.pop_front();
                continue;
            }
            //
            if(B.front()=='B'&&A.front()=='2')
            {
                 A.pop_front();
                 continue;
            }
            if(B.front()=='B'&&A.front()=='1')
            {
                B.pop_front();
                B.push_front('C');
                B.push_front('A');
                B.push_front('3');
                B.push_front('A');
                B.push_front('1');
                continue;
            }
            //
            if(B.front()=='C'&&A.front()=='2')
            {
                A.pop_front();
                B.pop_front();
                continue;
            }
            if(B.front()=='C'&&A.front()=='3')
            {
                B.pop_front();
                B.push_front('C');
                B.push_front('B');
                B.push_front('3');
                continue;
            }
            if(B.front()=='C'&&A.front()=='1')
            {
                B.pop_front();
                B.push_front('A');
                B.push_front('2');
                B.push_front('1');
                continue;
            }
            //
            break;
        }
        if(A.size()||B.size()) printf("0\n");
        else printf("1\n");
    }
    return 0;
}