#include <iostream>
#include <fstream>
using namespace std;
ifstream f("perle.in");
ofstream g("perle.out");
int v1[10003];char v2[10003];
int lg,pas;
int verifica()
{
    for (int i=1;i<=lg;i++)
    if (v1[i]!=int(v2[i])-48) return 0;
    return 1;
}
int b(int x)
{
    if (pas==lg)
    {
        if (verifica()==1)
        g<<"1"<<endl;
        else g<<"0"<<endl;
    }
}
int c(int x)
{
    if (pas==lg)
    {
        if (verifica()==1)
        g<<"1"<<endl;
        else g<<"0"<<endl;
    }
    else
    {
        if (v1[pas]==3) {g<<"0"<<endl; return 1;}
        else if (v1[pas]==1) {}
    }
}
int functie ()
{
    if (lg==1) g<<"1"<<endl;
    else if (v1[1]==1 && v1[2]==2 && lg==3 )g<<"1"<<endl;
    else if (lg==2) g<<"0"<<endl;
    else if (lg==3 && v1[1]==3) g<<"0"<<endl;
    else if( v1[1]==3 ) {pas=2; v2[1]=='1'; c(2);}
}
void citire()
{
    for (int i=1;i<=lg;i++)
    {
        f>>v1[i];
    }
}
int main()
{
    int n,ltot;
    f>>n;
    for (int i=1;i<=n;i++)
    {
        f>>lg;
        citire();
        pas=0;
        functie();
    }
    return 0;
}