#include <fstream>
using namespace std;

const int N=10009;
int stack[N],n;
char s[3*N],D;

ifstream in("perle.in");
ofstream out("perle.out");

inline bool A(int x)
{
    return x>0;
}

inline bool B(int x)
{
    return x==-2;
}

inline bool C(int x)
{
    return x==-3 || x==2;
}

inline bool perla21()
{
    return (stack[0]>1) && stack[stack[0]-1]==2 && B(stack[stack[0]]);
}

inline bool perla22()
{
    return stack[0]>4 && stack[stack[0]-4]==1 && A(stack[stack[0]-3]) && stack[stack[0]-2]==3 && A(stack[stack[0]-1]) && C(stack[stack[0]]);
}

inline bool perla31()
{
    return stack[0]>2 && stack[stack[0]-2]==3 && B(stack[stack[0]-1]) && C(stack[stack[0]]);
}

inline bool perla32()
{
    return stack[0]>2 && stack[stack[0]-2]==1 && stack[stack[0]-1]==2 && A(stack[stack[0]]);
}

inline bool perla()
{
    return perla21() || perla22() || perla31() || perla32();
}

inline bool cifra(char c)
{
    return '0'<=c && c<='9';
}

void get(int &x)
{
    while (!cifra(s[D]))
        D++;
    x=s[D++]-'0';
}

int main()
{
    int t,x;
    in>>t>>ws;
    while (t--)
    {
        in.getline(s,2*N);
        D=0;
        get(n);
        stack[0]=0;
        for (int i=1;i<=n;i++)
        {
            get(x);
            stack[++stack[0]]=x;
            while (perla())
            {
                if (perla21())
                {
                    stack[0]--;
                    stack[stack[0]]=-2;
                }
                if (perla22())
                {
                    stack[0]-=4;
                    stack[stack[0]]=-2;
                }
                if (perla31() || perla32())
                {
                    stack[0]-=2;
                    stack[stack[0]]=-3;
                }
            }
        }
        out<<(stack[0]==1)<<"\n";
    }
    return 0;
}