#include <bits/stdc++.h>

using namespace std;

string C;

int len(int poz,char s){
if(poz >= C.size())
    return C.size() + 1;
if(s == 'A')
    return poz + 1;
if(s == 'B'){
    if(C[poz] == '1'){
        if(poz + 4 >= C.size())
            return C.size() + 1;
        if(C[poz + 2] != '3')
            return C.size() + 1;
        return len(poz + 4 , 'C');
    }
    if(C[poz] == '2'){
        if(poz + 1 >= C.size())
            return C.size() + 1;
        return len(poz + 1 , 'B');
    }
    return poz;
}
if(C[poz] == '1'){
    if(poz + 2 >= C.size())
        return C.size() + 1;
    if(C[poz + 1] != '2')
        return C.size() + 1;
    return len(poz + 2 , 'A');
}
if(C[poz] == '2')
    return poz + 1;
if(C[poz] == '3'){
if(poz + 1 >= C.size())
    return C.size() + 1;
int k = len(poz + 1 , 'B');
if(k >= C.size())
    return C.size() + 1;
k = len(k , 'C');
return k;
}

}

void test_case(){
int n;
cin >> n;
C = "";
C.resize(n);
for(int i = 0;i < n; ++i)
    cin >> C[i];
if(len(0 , 'A') == n || len(0 , 'B') == n || len(0 , 'C') == n)
    cout << 1 << "\n";
else
    cout << 0 << "\n";
}

int main()
{
    freopen("perle.in" , "r" , stdin);
    freopen("perle.out" , "w" , stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin >> t;
    while(t--)
        test_case();
}