#include <bits/stdc++.h>
using namespace std;
ifstream f("perle.in");
ofstream g("perle.out");

#define int long long
const int Max = 1e5 + 1;
void nos()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}
char s[Max];
int n;
void read()
{
    f>>n;
    int i;
    for(i=1; i<=n; i++)
        f>>s[i];
}
int poz;
bool broken = 0;
void b();
void c();
void b()
{
    if(poz > n)
    {
        broken = 1;
        return;
    }

    if(s[poz] == '2')
    {
        ++poz;
        b();
    }
    else if(s[poz] == '1' and s[poz + 2] == '3')
    {
        poz+=4;
        c();
    }
    else
        broken = 1;
}
void c()
{
    if(poz > n)
    {
        broken = 1;
         return;
    }

    if(s[poz] == '2' )
    {
        poz++;
        return;
    }

    if(s[poz] == '1' and s[poz+1] == '2')
    {
        poz += 3;
        return;
    }
    if(s[poz] == '3')
    {
        ++poz;
        b();
        ++poz;
        c();
    }
    else
        broken = 1;
}
void solve()
{
    poz = 1;
    if(n==1)
    {
        g<<"1\n";
        return;
    }
    if(s[poz] == '2')
    {
        ++poz;
        b();
    }
    else if(s[poz] == '1' and s[poz + 2] == '3')
    {
        poz+=4;
        c();
    }
    else if(s[poz] == '2' )
        poz++;
    else if(s[poz] == '1' and s[poz+1] == '2')
        poz += 3;
    else if(s[poz] == '3')
    {
        ++poz;
        b();
        ++poz;
        c();
    }
    else
        broken = 1;
    g<<(broken ^ 1)<<'\n';
}
void restart()
{

}

int32_t main()
{
    nos();
    int teste;
    f>>teste;
    while(teste--)
    {
        read();
        solve();
        restart();
    }
    return 0;
}