#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <set>
#include <string>
#include <queue>

const long double PI = acos(-1);

using namespace std;

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

//#define fin cin
//#define fout cout

int teste;
int n, nn;
char c[10002];
char nou[10002];
int main(){
    
    
    
    fin >> teste;
    
    while( teste-- ){
        int crr = 1, start = 1; nn = 0;
        
        fin >> n;
        for( int i = 1 ; i <= n ; ++i ) fin >> c[i];
        
        for( int i = 0 ; i <= 10000 ; ++i ) nou[i] = 'X';
        
        
        if( c[crr] == '1' ){//initializare
            if( crr == n ) { nou[++nn] = 'A'; }
            else if( crr + 2 <= n && c[crr+2] == '3' ){
                nou[++nn] = '1';
                nou[++nn] = 'A';
                nou[++nn] = '3';
                nou[++nn] = 'A';
                nou[++nn] = 'C';
                crr += 4;
            }else{
                nou[++nn] = '1';
                nou[++nn] = '2';
                nou[++nn] = 'A';
                crr += 2;
            }
        }else if( c[crr] == '2' ){
            if( crr == n ) { nou[++nn] = 'A'; }
            else{
                nou[++nn] = '2';
                nou[++nn] = 'B';
                ++crr;
            }
        }else if( c[crr] == '3' ){
            if( crr == n ) { nou[++nn] = 'A'; }
            else{
                nou[++nn] = '3';
                nou[++nn] = 'B';
                nou[++nn] = 'C';
                crr += 2;
            }
        }//initializare
        
        bool corect = true;
        //fout << crr << "   ";
        
        while( crr <= n ){
            
            for( int i = start ; i <= crr && crr <= n ; ++i ){
                if( nou[i] == '1' || nou[i] == '2' || nou[i] == '3' ){
                    if( nou[i] != c[i] ){
                        corect = false; crr = n + 1;
                        break;
                    }
                }else if( nou[i] == 'A' || nou[i] == 'B' || nou[i] == 'C' ){
                    
                    if( c[i] == '1' ){
                        
                        if( i + 2 <= n && c[i+2] == '3' && crr + 4 <= n ){
                            
                            if( nou[i] == 'B' ){
                                nou[i] = '1';
                                nou[i + 1] = 'A';
                                nou[i + 2] = '3';
                                nou[i + 3] = 'A';
                                nou[i + 4] = 'C';
                                crr += 4;
                                
                            }else{
                                corect = false; crr = n + 1;
                                break;
                            }
                        }else if( c[i + 1] == '2' && crr + 2 <= n ){
                            if( nou[i] == 'C' ){
                                nou[i] = '1';
                                nou[i + 1] = '2';
                                nou[i + 2] = 'A';
                                crr += 2;
                            }else{
                                corect = false; crr = n + 1;
                                break;
                            }
                        }else{
                            nou[i] = '1';
                            if( i == n ) ++crr;
                        }
                        
                    }else if( c[i] == '2' ){
                        if( nou[i] == 'A' ){
                            nou[i] = '2';
                            if( i == n ) ++crr;
                        }else if( nou[i] == 'B' ){
                            nou[i] = '2';
                            nou[i + 1] = 'B';
                            ++crr;
                        }else{
                            nou[nn] = '2';
                            if( i == n ) ++crr;
                        }
                    }else if( c[i] == '3' ){
                        if( nou[i] == 'A' ){
                            nou[i] = '3';
                            if( i == n ) ++crr;
                        }else if( nou[i] == 'B' ){
                            corect = false; crr = n + 1;
                            break;
                        }else{
                            nou[i] = '3';
                            nou[i + 1] = 'B';
                            nou[i + 2] = 'C';
                            crr += 2;
                        }
                    }
                    
                }
                
            }
            
        }
        for( int i = 1 ; i <= n ; ++i ){
            if( nou[i] != c[i] ) corect = false;;
        }
        for( int i = n + 1 ; i <= n + 10 ; ++i ){
            if( nou[i] != 'X' ) corect = false;;
        }
        
        if( corect ) fout << 1 << "\n";
        else fout << 0 << "\n";
        
        
    }
    return 0;
}