#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define lowbit(i) (i&(-i))
#define fi first
#define se second
#define pi pair<int,int>
#define mp make_pair
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid (l+r>>1)
const int maxn=5e5+5;
inline int read(){
	char ch=getchar();int x=0;bool f=0;
	for(;!isdigit(ch);ch=getchar())if(ch=='-')f=1;
	for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
	if(f==1)x=-x;return x;
}
vector<pi>Q[maxn];
long long ans=0,c[maxn*4],s[maxn*4],tag[maxn*4];
int a[maxn],n,T,pos[maxn];
void build(int rt,int l,int r){
    c[rt]=s[rt]=tag[rt]=0;
    if(l==r){return;}
    build(ls,l,mid),build(rs,mid+1,r);
}
void pushx(int rt,int l,int r,int x){
    tag[rt]=x,c[rt]=x;s[rt]=(r-l+1)*x;
}
void push(int rt,int l,int r){
    if(tag[rt]){
        pushx(ls,l,mid,tag[rt]);
        pushx(rs,mid+1,r,tag[rt]);
        tag[rt]=0;
    }
}
void change(int rt,int l,int r,int L,int R,int x){
    if(l>R||r<L){return ;}
    if(l>=L&&r<=R){
        pushx(rt,l,r,x);
        return ;
    }
    push(rt,l,r);
    change(ls,l,mid,L,R,x),change(rs,mid+1,r,L,R,x);
    c[rt]=min(c[ls],c[rs]);s[rt]=s[ls]+s[rs];
}
int query(int rt,int l,int r,int L,int R){
    if(l>R||r<L){return 0;}
    //cout<<R<<" "<<L<<" "<<l<<" "<<r<<" "<<s[rt]<<endl;
    if(l>=L&&r<=R)return s[rt];
    push(rt,l,r);
    return query(ls,l,mid,L,R)+query(rs,mid+1,r,L,R);
}
int find(int rt,int l,int r,int x){
    if(l==r)return l;
    push(rt,l,r);
    if(c[ls]<x){
        return find(ls,l,mid,x);
    }
    else return find(rs,mid+1,r,x);
}
struct Sam
{
	unordered_map<int,int> ch[maxn];
    int len[maxn],fa[maxn];
	int t=1,tot=1;
    void clear(){
        for(int i=1;i<=tot;i++)len[i]=fa[i]=0,ch[i].clear();
        t=1,tot=1;
    }
	void ins(int x,int id)
	{
		int p=t;t=++tot;len[t]=len[p]+1;pos[t]=id;
		for(;p&&!ch[p][x];p=fa[p])ch[p][x]=t;
		if(!p){fa[t]=1;return;}int q=ch[p][x];
		if(len[q]==len[p]+1){fa[t]=q;return;}
		len[++tot]=len[p]+1;fa[tot]=fa[q];
        fa[q]=fa[t]=tot;pos[tot]=id;
		ch[tot]=ch[q];
		for(int i=p;ch[i][x]==q;i=fa[i])ch[i][x]=tot;
	}
    void work(){
        for(int i=2;i<=tot;i++){
            Q[pos[i]].pb(mp(pos[i]-len[i]+1,pos[i]-len[fa[i]]));
        }
        build(1,1,n);
        for(int i=1;i<=n;i++){
            int k=find(1,1,n,a[i]);
            change(1,1,n,k,i,a[i]);
            for(auto j:Q[i]){
                ans+=query(1,1,n,j.fi,j.se);
            }
        }
    }
	
}S;
void solve(){
    S.clear();
    n=read();ans=0;
    for(int i=1;i<=n;i++)a[i]=read(),S.ins(a[i],i);
    S.work();
    for(int i=1;i<=n;i++)Q[i].clear();
    cout<<ans<<endl;
}

signed main(){
    T=read();
    while(T--)solve();
    return 0;
}