#include <iostream>
#include <fstream>

using namespace std;

 int n , m;
 char a[ 100 * 100 + 2], x[ 100 * 110 ];
  int sv;
  int verif ( int p ){
      for ( int i = 1 ; i <= p ; i++ ){
          switch ( x [ i ] ){
              case 'a':{ x[ i ] = a [ i ]; break;}
              case 'b':{
                  if ( a[ i ] == '1'){
                      for ( int j = p + 4; j >= i + 5; j--)
                          x [ j ] = x [ j - 4 ];
                          x [ i ] = '1'; x [ i + 1 ] = 'a'; x[ i + 2  ] ='3'; x[ i + 3 ] = 'a'; x [ i + 4 ] = 'c';
                          p += 4;
                          break;}
                 if ( a[ i ] == '2'){
                     for ( int j = p + 1 ; j >= i + 2; j--)
                         x [ j ] = x [ j - 1 ];
                         x [ i ] = '2'; x [ i + 1 ] = 'b';
                         p += 1;
                         break;}}
             case 'c':{
                  if ( a[ i ] == '1'){
                      for ( int j = p + 2; j >= i + 3 ; j-- )
                       x [ j ] = x [ j - 2 ];
                       x [ i ] = '1'; x [ i + 1 ] = '2'; x [ i + 2 ] = 'a';
                       p += 2; break;}
                 if ( a[ i ] == '3'){
                     for ( int j = p + 2; j >= i + 3; j-- )
                      x[ j ] = x [ j - 2 ];
                      x [ i ] = '3'; x[ i + 1 ] = 'b'; x[ i + 2 ] = 'c';
                      p += 2; break;}
                if  (a [ i ] == '2'){
                     x [ i ] = '2';
                     break;}}}}
        if ( p != m )
         return 0;
        else{
            sv = 0;
            for ( int k = 1 ; k <= m ; k++)
              if (a [ k ] != x [ k ]){
                sv = 1;
                break;}
        if (!sv)
        return 1;
        else
        return 0;}}




int main(){
    ifstream cin ("perle.in");
    ofstream cout ("perle.out");
       cin >> n;
       bool sw;
       for ( int i = 1; i <= n; i++ ){
           cin >> m;
             for ( int j = 1; j <= m; j++)
               cin >> a[ j ];
               sw = 0;
                    x[ 1 ] = 'a';
                    if (verif(1) == 1){
                        cout << 1 << '\n';
                        sw = 1;}
                    x[ 1 ] = 'b';
                    if (verif(1) == 1 && sw == 0){
                        cout << 1 << '\n';
                        sw = 1;}
                    x[ 1 ] = 'c';
                    if (verif(1) == 1 && sw == 0){
                        cout << 1 << '\n';
                        sw = 1;}
                if (sw == 0)
                  cout << 0 << '\n';}}