#include <stack>
#include <fstream>
#include <iostream>

using namespace std;

int i,n,t,nr;
char s[10000];

stack<char> sp;

#define B 1
#define C 2

int main()
{
    fstream f("perle.in",ios::in),g("perle.out",ios::out);
    f>>t;
    while(t--)
    {
        f>>n;
        for(i=0;i<n;i++){f>>nr;s[i]=nr;}
        while(!sp.empty())sp.pop();
        if(n==1){g<<"1\n";continue;}
        if(s[0]==2){sp.push(B);i=1;}
        else if(s[0]==3){sp.push(C);sp.push(B);i=1;}
        else {sp.push(C);i=0;}
        while(i<n)
        {
            if(sp.empty()){sp.push(0);break;}
            else if(sp.top()==B)
            {
                if(s[i]==2){i++;continue;}
                else if(s[i]==1)
                {
                    if(s[i+2]!=3)break;
                    i+=4;
                    sp.pop();
                    sp.push(C);
                }
                else break;
            }
            else if(sp.top()==C)
            {
                if(s[i]==2)
                {
                    sp.pop();
                    i++;
                }
                else if(s[i]==3)
                {
                    sp.pop();
                    sp.push(C);
                    sp.push(B);
                    i++;
                }
                else if(s[i]==1)
                {
                    if(i>n-3)break;
                    if(s[i+1]!=2)break;
                    sp.pop();
                    i+=3;
                }
                else break;
            }
        }
        if(sp.empty())g<<"1\n";
        else g<<"0\n";
    }
}