#include <fstream>

using namespace std;
int sir[10010],i,j,k,t,n;
bool ok;
void perle(string s,int k)
{
    int sz=s.size();
    if(sz+k-1>n) return;
    if(k==n+1 and s.empty()) ok=true;
    if(s.empty()) return;
    if(s[0]<'A' and s[0]-48==sir[k])
    {
        s=s.substr(1);
        k++;
    } else if (s[0]<'A') return; else
    if(s[0]=='A')
    {
        s=s.substr(1);
        k++;
    } else
    if(s[0]=='B')
    {
        if(sir[k]==1) {s=s.substr(1); s="A3AC"+s; k++;} else
        if(sir[k]==2) k++; else
        if(sir[k]==3) return;
    } else
    if(s[0]=='C')
    {
        if(sir[k]==2) {s=s.substr(1); k++; } else
        if(sir[k]==3) {s="B"+s; k++;} else
        if(sir[k]==1) {s=s.substr(1); s="2A"+s; k++; }
    }
    perle(s,k);
}
int main()
{
    ifstream fi("perle.in");
    ofstream fo("perle.out");
    fi>>t;
    while(t--)
    {
        fi>>n;
        for(i=1;i<=n;i++) fi>>sir[i];
        ok=0;
        perle("A",1);//sir curent, pozitia in sir
        if(ok==1) {fo<<"1\n"; continue; }
        perle("B",1);
        if(ok==1) {fo<<"1\n"; continue; }
        perle("C",1);
        if(ok==1) {fo<<"1\n"; continue; }
        fo<<"0\n";
    }
    return 0;
}