#include<fstream>
#define DIM 11005
using namespace std;
int t, n, i, x;
char s[DIM], v[DIM];
ifstream f("perle.in");
ofstream g("perle.out");
int rezolva(char c)
{
    int i, u = 1;
    s[1] = c;
    for(i = 1; i <= n; i++)
        {
        if(u == 0)
        {
            return 0;
        }
        if(s[u] >= '1' && s[u] <= '3')
        {
            if(s[u] == v[i])
            {
                u--;
            }
            else
            {
                return 0;
            }
            continue;
        }
        if(s[u] == 'a')
        {
            u--;
            continue;
        }
        if(s[u] == 'b')
        {
            if(v[i] == '3')
            {
                return 0;
            }
            if(v[i] == '1')
            {
                s[u] = 'c';
                s[u + 1] = 'a';
                s[u + 2] = '3';
                s[u + 3] = 'a';
                u += 3;
            }
            continue;
        }
        if(v[i] == '2')
        {
            u++;
        }
        if(v[i] == '3')
        {
            s[u] = 'c';
            s[u + 1] = 'b';
            u++;
        }
        if(v[i] == '1')
        {
            s[u] = 'a';
            s[u + 1] = '2';
            u++;
        }
    }
    if(u == 0)
    {
        return 1;
    }
    return 0;
}
int main(){
    f>> t;
    while(t--)
    {
        f>>n;
        for(i = 1; i <= n; i++)
        {
            f>>x;
            v[i] = x + '0';
        }
        if(rezolva('a'))
        {
            g<<"1\n";
            continue;
        }
        if(rezolva('b'))
        {
            g<<"1\n";
            continue;
        }
        if(rezolva('c'))
        {
            g<<"1\n";
            continue;
        }
        g<<"0\n";
    }
    return 0;
}