#include <iostream>
#include <fstream>

bool sePoate(char sir[], int i, int n, bool c, bool b)
{
    if(i == n)
    {
        if(c == true && sir[i] != '2')
        {
            return false;
        }
        if(b == true)
        {
            return false;
        }
        return true;
    }
    else if(i > n)
    {
        return false;
    }
    else{

        if(sir[i] == '1')
        {
            if(i == n - 2 && sir[i + 1] == '2')
            {
                return true;
            }
            else
            {

                if(sir[i + 2] == '3')
                {
                    return sePoate(sir, i + 4, n, true, false);
                }
            }
        }
        else if(sir[i] == '2')
        {
            if(b == true)
            {
                return sePoate(sir, i + 1, n, false, true);
            }
            else{
                return false;
            }

        }
        else {
            if(c == true)
            {
                return sePoate(sir, i + 1, n, false, true);
                return sePoate(sir, i + 2, n, true, false);
            }
        }
    }
}

int main()
{
    std::ifstream in("perle.in");
    std::ofstream out("perle.out");

    int N;
    in >> N;

    while(N-- > 0)
    {
        int lung_sir;
        char sir[10002];

        in >> lung_sir;
        for(int i = 1; i <= lung_sir; ++i){
            in >> sir[i];
        }

        if(lung_sir == 1 || sePoate(sir, 1 ,lung_sir, true, true))
        {
            out << 1 << '\n';
        }
        else{
            out << 0 << '\n';
        }
    }

    in.close();
    out.close();
    return 0;
}