#include<bits/stdc++.h>
using namespace std;
int e[10],o[12],pp;
vector<int>kc[1010010];
void dfs(int x){
    if(x==9){
        int z=0;
        for(int i=1;i<=8;i++)z+=e[i],o[i]=e[i];
        o[9]=o[10]=0;
        if(z%3)return;
        bool gg=0;
        for(int i=1;i<=10;i++){
            if(o[i]<0){gg=1;break;}
            if(o[i]>=3)o[i]-=3;if(o[i]>=3)o[i]-=3;
            if(o[i])o[i+2]-=o[i],o[i+1]-=o[i];
        }
        if(!gg){
            int jb=0,xx=0;
            for(int i=1;i<=8;i++)
                jb=jb*5+min(e[i],4),xx=xx*4+(e[i]%3);
            kc[jb].push_back(xx);
        }
        return;
    }
    for(int i=0;i<=6;i++)e[x]=i,dfs(x+1);
}
int n,a[101000],P5[10],tp[10],xp[100100];
vector<int>g[100100];
long long ans;
int p[38],hs,nt[10];
void sol(){
    memset(tp,0,sizeof(tp));
    scanf("%d",&n);
    hs=0;
    ans=0;
    xp[0]=0,g[0].push_back(0);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        tp[a[i]]++;if(tp[a[i]]>=3)tp[a[i]]%=3;
        int xx=0;
        for(int j=1;j<=8;j++)xx=xx*3+tp[j];
        g[xx].push_back(i),xp[i]=xx;
        int kn=0,PP=0;
        for(int j=hs;j;j--)if(a[i]==a[p[j]])PP=j,kn++;
        if(kn<4)p[++hs]=i;
        else{
            for(int j=PP;j<hs;j++)p[j]=p[j+1];
            p[hs]=i;
        }
        memset(nt,0,sizeof(nt));int st=0;
        for(int j=hs;j;j--){
            int o=a[p[j]];
            if(nt[o]<4)st+=P5[8-o];
            nt[o]++;
            for(int m_:kc[st]){
                int mm=0;
                for(int i=1;i<=8;i++){
                    int e=3-((m_>>(16-i*2))&3)+tp[i];
                    if(e>=3)e-=3;
                    mm=mm*3+e;
                }
                int l=lower_bound(g[mm].begin(),g[mm].end(),p[j-1])-g[mm].begin();
                int r=lower_bound(g[mm].begin(),g[mm].end(),p[j])-g[mm].begin();
                ans+=r-l;
            }
        }
    }
    for(int i=0;i<=n;i++)g[xp[i]].clear();
    printf("%lld\n",ans);
}
int main(){
    P5[0]=1;
    for(int i=1;i<=8;i++)P5[i]=P5[i-1]*5;
    dfs(1);
    int T;scanf("%d",&T);while(T--)sol();
    return 0;
}