#include <fstream>
using namespace std;
/**
A -> 1 | 2 | 3
B -> 2B | 1A3AC
C -> 2 | 3BC | 12A
**/
const int NMAX = 1e4;
char v[NMAX + 1];
int b ( int poz, int n );
int c ( int poz, int n );
int b ( int poz, int n ) {
    if ( v[poz] == 2 )
        return b ( poz + 1, n );
    if ( poz + 3 < n && v[poz] == 1 && v[poz + 2] == 3 )
        return c ( poz + 4, n );
    return 0;
}
int c ( int poz, int n) {
    if ( v[poz] == 2 )
        return poz + 1;
    if ( poz + 2 < n && v[poz] == 3 )
        return c ( b ( poz + 1, n ), n );
    if ( poz + 2 < n && v[poz] == 1 && v[poz + 1] == 2 )
        return poz + 3;
    return 0;
}
ifstream fin("perle.in");
ofstream fout("perle.out");
int main() {
    int t, n, i;
    fin >> t;
    while ( t-- ) {
        fin >> n;
        for ( i = 0; i < n; i++ ) {
            fin >> v[i];
            v[i] -= '0';
        }
        fout << ( n == 1 || b(0, n) == n || c(0, n) == n ) << '\n';

    }

    return 0;
}