#include <iostream>
#include <cstdio>
#include <cstring>

#define mmx 10005

using namespace std;

char s[mmx];
bool ok;

void solve() ;

int main()
{
    int n ;
    freopen( "perle.in" , "r" , stdin ) ;
    freopen( "perle.out" , "w" , stdout ) ;
    scanf( "%d" , &n ) ;
    for ( ; n ; n -- )
        solve() ;
    return 0;
}

void recurs()
{
    if ( not ok )
        return ;
    int x = strlen(s) ;
    if ( x == 1 )
    {
        ok = 0 ;
        return ;
    }
    for ( int i = 0 ; i < x ; i ++ )
    {
        if ( isdigit(s[i]) )
        {
            char aux = s[i] ;
            s[i] = 'A' ;
            recurs() ;
            if ( s[i] == '2' )
            {
                s[i] = 'C' ;
                recurs() ;
            }
            s[i] = aux ;
        }
        if ( s[i] == '2' && s[i+1] == 'B' )
        {
            char aux[mmx] ;
            strcpy( aux , s ) ;
            strcpy( s + i , s + i + 1 ) ;
            recurs() ;
            strcpy( s , aux ) ;
            continue ;
        }
        if ( s[i] == '1' && s[i+1] == 'A' && s[i+2] == '3' && s[i+3] == 'A' && s[i+4] == 'C' )
        {
            char aux[mmx] ;
            strcpy( aux , s ) ;
            strcpy( s + i , s + i + 4 ) ;
            s[i] = 'B' ;
            recurs() ;
            strcpy( s , aux ) ;
            continue ;
        }
        if ( s[i] == '3' && s[i+1] == 'B' && s[i+2] == 'C' )
        {
            char aux[mmx] ;
            strcpy( aux , s ) ;
            strcpy( s + i , s + i + 2 ) ;
            recurs() ;
            strcpy( s , aux ) ;
            continue ;
        }
        if ( s[i] == '1' && s[i+1] == '2' && s[i+2] == 'A' )
        {
            char aux[mmx] ;
            strcpy( aux , s ) ;
            strcpy( s + i , s + i + 2 ) ;
            s[i] = 'C' ;
            recurs() ;
            strcpy( s , aux ) ;
            continue ;
        }
    }
}

void solve()
{
    int t ;
    scanf( "%d" , &t ) ;
    for ( int i = 0 ; i < t ; i ++ )
    {
        int nr ;
        scanf( "%d" , &nr ) ;
        s[i] = (char) nr + 48 ;
    }
    s[t] = 0 ;
    ok = 1 ;
    recurs() ;
    if ( not ok )
    {
        printf( "1\n" ) ;
        return ;
    }
    printf( "0\n" ) ;
}