#include <bits/stdc++.h>  
#define ll long long  
using namespace std;  
const long long mod = 20020219, inf = 1e18;  
ll n, m, k, q,l,r,ans=0,all=0;
vector<int> mmp[50005]{};
deque<ll> que[10]{};
ll arr[200005]{};
int num[19]{},pw[10]{};
vector<int> pre(9),suf(9),temp(9);
void work()
{
    pw[0]=1;
    for(int i=1;i<=9;i++)
    {
        pw[i]=pw[i-1]*3;
    }
}
void dfs(int depth,int st,ll pos) 
{
    if(depth==7)
    {   auto iter=lower_bound(mmp[st].begin(),mmp[st].end(),pos);
        //if(pos!=inf) iter--;
        //cout<<st<<'a';
        //for(auto i:mmp[st]) cout<<i<<'b';
        //cout<<'\n';
        ans+=max(0,(int)(iter-mmp[st].begin()));
        return ;
    }
    //cout<<st;
    //cout<<depth<<' ';
    for(int i=0;i<=min({2,pre[depth],pre[depth+1],pre[depth+2]});i++)
    {
        int nst=st;
        if(i)
        {
            if(pre[depth]%3>=i) nst-=i*pw[depth];
            else nst+=(3-i)*pw[depth];
            if(pre[depth+1]%3>=i) nst-=i*pw[depth+1];
            else nst+=(3-i)*pw[depth+1];
            if(pre[depth+2]%3>=i) nst-=i*pw[depth+2];
            else nst+=(3-i)*pw[depth+2];
        }
        //cout<<nst<<'\n';
        pre[depth]-=i,pre[depth+1]-=i,pre[depth+2]-=i;
        num[depth]+=i,num[depth+1]+=i;num[depth+2]+=i;
        ll npos=inf;
        if(i)
        npos=min({npos,que[depth][num[depth]-1],que[depth+1][num[depth+1]-1],que[depth+2][num[depth+2]-1]});
        dfs(depth+1,nst,npos);
        pre[depth]+=i,pre[depth+1]+=i,pre[depth+2]+=i;
        num[depth]-=i,num[depth+1]-=i;num[depth+2]-=i;
    }
}
void solve() { 
    for(int i=0;i<=50000;i++) mmp[i].clear();
    for(int i=1;i<=8;i++) que[i].clear();
    cin>>n;
    all=0;
    for(int i=1;i<=n;i++)
    {
        cin>>arr[i];
    }
    for(int i=0;i<9;i++) pre[i]=0;
    ans=0;
    mmp[0].push_back(0);
    int state=0;
    for(int i=1;i<=n;i++)
    {  // cout<<arr[i]<<'a';
        que[arr[i]].push_front(i);
        while(que[arr[i]].size()>=6) que[arr[i]].pop_back();
        pre[arr[i]]++;
        if(pre[arr[i]]%3==0) state-=2*pw[arr[i]];
        else state+=pw[arr[i]];
        all=state;
        dfs(1,all,inf); 
        mmp[state].push_back(i);
    }
    cout<<ans<<'\n';
}
int main() {  
    //ios::sync_with_stdio(false);  
    //cin.tie(0);  
    work();
    int T = 1;  
    cin >> T; 
    while(T--) {  
        solve();  
    }  
    return 0;  
}
/*

*/