#include <iostream>

using namespace std;
int cnt=0;
int v[100005];
int b[10];
int stare[800][10];
int sumus[800];
//int aricifrecarici[6000000];
const int bulan=50;
void bkt(int poz)
{
    if(poz==7)
    {
        for(int i=1;i<=8;i++)
        {
            b[i]=0;
        }
        for(int i=1;i<=6;i++)
        {
            b[i]+=v[i];
            b[i+1]+=v[i];
            b[i+2]+=v[i];
        }
        cnt++;
        for(int i=1;i<=8;i++)
        {
            stare[cnt][i]=b[i];
            sumus[cnt]=sumus[cnt]*7+b[i];
        }
        //aricifrecarici[sumus[cnt]]++;
        return;
    }
    for(int i=0;i<=2;i++)
    {
        v[poz]=i;
        bkt(poz+1);
    }
}
int f[10];
int f2[10];
int pow7[10];
int fremask[6000000];
void bktadd(int poz,int sum,int semn)
{
    if((poz==2 && v[1]>=3) || (poz==3 && v[2]>=5) || (poz==8 && v[7]>=5) || (poz==9 && v[8]>=3))
    {
        return ;
    }
    if(poz==9)
    {
        fremask[sum]+=semn;
        return;
    }
    bktadd(poz+1,sum*7+f[poz],semn);
    if(f[poz]>=3)
    {
        f[poz]-=3;
        bktadd(poz+1,sum*7+f[poz],semn);
        f[poz]+=3;
    }
    if(f[poz]>=6)
    {
        f[poz]-=6;
        bktadd(poz+1,sum*7+f[poz],semn);
        f[poz]+=6;
    }
}
int fre[10];
int fre2[10];
long long divide(int st,int dr)
{
    int i,j,kuk;
    long long rez=0;
    if(dr-st<=bulan)
    {
        for(i=st;i<=dr;i++)
        {
            for(j=1;j<=8;j++)
            {
                fre[j]=0;
            }
            for(j=i;j<=dr;j++)
            {
                fre[v[j]]++;
                if((j-i)%3==2)
                {
                    int pos=1;
                    for(int z=1;z<=8;z++)
                        fre2[z]=fre[z];
                    for(int z=1;z<=6;z++)
                    {
                        if(fre2[z]<0)
                        {
                            pos=0;
                            break;
                        }
                        fre2[z]=fre2[z]%3;
                        fre2[z+1]-=fre2[z];
                        fre2[z+2]-=fre2[z];
                    }
                    if(fre2[7]%3==0 && fre2[8]%3==0 && fre2[7]>=0 && fre2[8]>=0)
                    {
                        rez+=pos;
                    }
                }
            }
        }
        return rez;
    }
    int mij=(st+dr)/2;
    for(i=1;i<=8;i++)
    {
        f[i]=0;
    }
    bktadd(1,0,1);
    for(i=mij+1;i<=dr;i++)
    {
        f[v[i]]++;
        if(f[v[i]]>=7)
        {
            f[v[i]]-=3;
        }
        bktadd(1,0,1);
    }
    for(int st2=1;st2<=729;st2++)
    {
        for(j=1;j<=8;j++)
            f2[j]=0;
        int suma=sumus[st2];
        for(i=mij;i>=st;i--)
        {
            f2[v[i]]++;
            suma-=pow7[v[i]];
            if(f2[v[i]]>stare[st2][v[i]])
            {
                suma+=3*pow7[v[i]];
                f2[v[i]]-=3;
            }
            rez+=fremask[suma];
        }
    }
    for(i=1;i<=8;i++)
    {
        f[i]=0;
    }
    bktadd(1,0,-1);
    for(i=mij+1;i<=dr;i++)
    {
        f[v[i]]++;
        if(f[v[i]]>=7)
        {
            f[v[i]]-=3;
        }
        bktadd(1,0,-1);
    }
    rez=rez+divide(st,mij-1);
    rez=rez+divide(mij+1,dr);
    return rez;
}
int main()
{
    long long n,i,j,k,l,r,op,t,bestcase,m,mmax;
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>t;
    bkt(1);
    pow7[8]=1;
    for(i=7;i>=1;i--)
    {
        pow7[i]=pow7[i+1]*7;
    }
    for(op=1;op<=t;op++)
    {
        cin>>n;
        for(i=1;i<=n;i++)
        {
            cin>>v[i];
        }
        cout<<divide(1,n)<<'\n';
    }
    return 0;
}