#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=729;
#define int long long
typedef long long ll;
typedef pair<ll,ll> PII;
int n,m,k;
ll a[N],c[N],tg[N],dep[N];
array<int,8> b[1010];
// char s[N];
vector<int> e[N];
int now[10],now2[10];
array<int,8> s[N];
int p[N];
bool tf[M*10];
void dfs(int x){
    if(x==6){
        int state=0;
        for(int i=5;i>=0;i--) state=state*3+c[i];
        for(int i=0;i<6;i++){
            // for(int u=1;u<=c[i];u++)
            // {
            b[state][i]+=c[i];
            b[state][i+1]+=c[i];
            b[state][i+2]+=c[i];
            // }
        }
        // tg[state]=0;
        // for(int i=7;i>=0;i--){
        //     tg[state]=tg[state]*3+(b[state][i]%3);
        // }
        // cout<<state<<endl;
        // able.insert(state);
    }else{
        for(int i=0;i<3;i++){
            c[x]=i;
            dfs(x+1);

        }
    }
}

bool cmp(array<int,8> &a1,array<int,8> &a2){
    for(int i=0;i<8;i++) if(a1[i]<a2[i]) return false;
    return true;
}

int query(array<int,8> &ar,int state){
    if(s[e[state].back()]>=ar) return e[state].size()-1;
    int l=0,r=e[state].size()-1;
    while(l<r){
        int mid=l+r+1>>1;
        if(cmp(s[e[state][mid]],ar)) l=mid;
        else r=mid-1;
    }
    // if(l>0) cout<<"--"<<l<<endl;
    return l;
}

void __(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        a[i]--;
    }
    array<int,8> ar;
    for(int i=0;i<8;i++) ar[i]=0;
    s[0]=ar;
    memset(now,0,sizeof now);

    for(int i=1;i<=n;i++){
        ar[a[i]]++;
        s[i]=ar;
        // cout<<s[i]<<" ";
    }
    for(int i=0;i<=M*10;i++){
         e[i].clear();
         array<int,8> res;
         for(int j=0;j<8;j++) res[j]=1e9;
         s[n+1]=res;
         e[i].push_back(n+1);
    }
    // cout<<endl;
    ll ans=0;
    for(int i=0;i<M;i++) p[i]=0;
    for(int i=n;i>=0;i--){
        // memset(tf,false,sizeof tf);
        for(int j=0;j<M;j++){
            array<int,8> nw;
            int t=j;

            for(int k=0;k<8;k++){
                nw[k]=(s[i][k]+b[j][k]%3)%3;
                t/=3;
            }
            
            int state=0;
            for(int k=7;k>=0;k--) state=state*3+nw[k];
            // assert(!tf[state]);
            tf[state]=1;
            // if(j==1){
            //     for(int k=0;k<8;k++) cout<<s[i][k]<<" ";
            //     cout<<endl;
            //     for(int k=0;k<8;k++) cout<<nw[k]<<" ";
            //     cout<<endl;
            //     cout<<endl;
            // }
            array<int,8> least;
            for(int k=0;k<8;k++) least[k]=s[i][k]+b[j][k];
            ll tt=query(least,state);
            ans+=tt;
            // if(tt>0) cout<<i<<" "<<j<<" "<<tt<<endl;
        }
        int state=0;
        for(int j=7;j>=0;j--) state=state*3+(s[i][j]%3);
        e[state].push_back(i);
    }
    printf("%lld\n",ans);
}
//2*1 1*2
//2 2 2

signed main(){
    
    dfs(0);
    // cout<<able.size()<<endl;
    int _=1;
    cin>>_;
    while(_--){
        __();
    }
}