#include<cstdio>
#include<deque>
using namespace std;
deque<char> A,B;
int n,t,i,x;
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('0'+x);
        }
        if(n==1)
        {
            printf("1\n");
            continue;
        }
        if(A[0]=='1')
        {
            if(n<3) B.push_back('A');
            else if(n<5) B.push_back('C');
            else B.push_back('B');
        }
        else if(A[0]=='2')
        {
            B.push_back('B');
        }
        else B.push_back('C');
        while(A.size() && B.size())
        {
            if(B.front()==A.front()) {B.pop_front(); A.pop_front(); continue;}
            if(B.front()=='A') {B.pop_front(); A.pop_front(); continue;}
            if(B.front()=='B' && A.front()=='3') break;
            if(B.front()=='B' && A.front()=='2') {A.pop_front(); continue;}
            if(B.front()=='B')
            {
                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()=='1')
            {
                B.pop_front();
                B.push_front('A');
                B.push_front('2');
                B.push_front('1');
                continue;
            }
            if(B.front()=='C')
            {
                B.push_front('B');
                B.push_front('3');
                continue;
            }
            break;
        }
        if(A.size() || B.size()) printf("0\n");
        else printf("1\n");
    }
    return 0;
}