#include <fstream>
#include <string.h>
using namespace std;
#define lgMax 10001

int lg;
char s[lgMax], st[lgMax];

bool transf(char) ;

int main()
{
    int i, j, n, perla, ok;
    
    freopen("perle.in", "r", stdin);
    freopen("perle.out", "w", stdout);
    
    scanf("%d", &n);
    for(i = 0; i < n; ++i)
    {
        scanf("%d", &lg);
        for(j = 0; j < lg; ++j) scanf("%s ", s + j);
        
        ok = 0;
        for(perla = 0; perla < 3 && !ok; ++perla)
            if(transf(char('A' + perla))) ok = 1;
        
        if(ok) printf("1\n");
        else printf("0\n");
    }
    
    return 0;
}

bool transf(char c)
{
    int vf = 0, j, nr;
    // nr - cate numere am introdus in stiva pana la un moment dat
    
    for(nr = 1, st[0] = c, j = 0; vf >= 0 && j < lg; ++j)
    {
        c = st[vf]; --vf;
        
        if(s[j] == c) continue;
        if('1' <= c && c <= '3') return 0;
        if('A' <= s[j] && s[j] <= 'C') return 0;
        if(nr > lg) return 0;
        
        switch(c)
        {
            case 'A': break;
            case 'B':
            {
                switch(s[j])
                {
                    case '1':
                    {
                        if(nr + 4 > lg) return 0;
                        else
                        {
                            st[++vf] = 'C';
                            st[++vf] = 'A';
                            st[++vf] = '3';
                            st[++vf] = 'A';
                            nr += 4;
                        }
                        break;
                    }
                    case '2':
                    {
                        if(nr + 1 > lg) return 0;
                        else
                        {
                            st[++vf] = 'B';
                            nr++;
                        }
                        break;
                    }
                    case '3': return 0;
                }
                break;
            }
            case 'C':
            {
                switch(s[j])
                {
                    case '1':
                    {
                        if(nr + 2 > lg) return 0;
                        else
                        {
                            st[++vf] = 'A';
                            st[++vf] = '2';
                            nr += 2;
                        }
                        break;
                    }
                    case '2': break;
                    case '3':
                    {
                        if(nr + 2 > lg) return 0;
                        else
                        {
                            st[++vf] = 'C';
                            st[++vf] = 'B';
                            nr += 2;
                        }
                        break;
                    }
                }
                break;
            }
        }
    }
    
    if(nr == lg) return 1;
    return 0;
}