#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("perle.in");
ofstream fout("perle.out");
int N,t,tt,L[12],a[10003];
int ok,nr[4];
string v[4][4];
int islet(char c)
{
    if(c=='A' || c=='B' || c=='C')return 1;
    return 0;
}
void rec(int i,string s)
{
    if(s.size()>L[t] || ok==1)return;
    string s2="";
    while(!islet(s[i]) && i<s.size() && a[i+1]==s[i]-'0')
        i++;
    if(!islet(s[i]) && i<s.size() && a[i+1]!=s[i]-'0')return ;
    if(i==s.size())
    {
        if(s.size()==L[t])ok=1;
        return;
    }
    else
    {
        for(int j=1;j<=nr[s[i]-'A'+1] && ok==0;j++)
        {
            s2="";
            if(i!=0)
            s2.append(s,0,i);
            s2.append(v[s[i]-'A'+1][j]);
            if(i+1<s.size())
            s2.append(s.begin()+i+1,s.end());
            rec(i,s2);
        }
    }

}
int main()
{
    fin>>N;
    v[1][1]="1";v[1][2]="2";v[1][3]="3";
    v[2][1]="2B";v[2][2]="1A3AC";
    v[3][1]="2";v[3][2]="3BC";v[3][3]="12A";
    nr[1]=3;nr[2]=2;nr[3]=3;
    for(t=1;t<=N;t++)
    {
        ok=0;
        fin>>L[t];
        for(tt=1;tt<=L[t];tt++)
            fin>>a[tt];
        int i=0;
        rec(i,"A");
        if(ok==0)rec(i,"B");
        if(ok==0)rec(i,"C");
        fout<<ok<<'\n';
    }
    return 0;
}