#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
#define int long long
typedef long long ll;
typedef pair<ll,ll> PII;
int n,len1,len2;
char s1[N],s2[N];

int a[N];
int aa[N];

int sa[N],height[N],rnk[N],id[N],oldrnk[N<<1];
int key1[N],cnt[N];
// int st[N][20];
int ST[N][30];
int le[N],ri[N];
bool cmp(int x,int y,int w){
	return (oldrnk[x]==oldrnk[y])&&(oldrnk[x+w]==oldrnk[y+w]);
}

void getsa(int s[]){
	for(int i=0;i<=(n<<1);i++){
		sa[i]=0,height[i]=0,rnk[i]=0,id[i]=0,oldrnk[i]=0,key1[i]=0,cnt[i]=0;
	}
	
	int m=n+1,p,w;
	for(int i=1;i<=n;i++){
		rnk[i]=s[i];
		cnt[rnk[i]]++;
	}
	for(int i=1;i<=m;i++) cnt[i]+=cnt[i-1];
	for(int i=n;i>=1;i--){//对长度为1的关键字桶排序
		sa[cnt[rnk[i]]--]=i;
	}   
	for(w=1;;w<<=1,m=p){
		p=0;
		for(int i=n;i>n-w;i--) id[++p]=i;
		for(int i=1;i<=n;i++){
			if(sa[i]>w) id[++p]=sa[i]-w;    
		}
		for(int i=0;i<=n+1;i++) cnt[i]=0;
		for(int i=1;i<=n;i++){
			key1[i]=rnk[id[i]];
			cnt[key1[i]]++;
		}
		for(int i=1;i<=m;i++) cnt[i]+=cnt[i-1];
		for(int i=n;i>=1;i--){
			sa[cnt[key1[i]]--]=id[i];
		}
		for(int i=1;i<=n;i++) oldrnk[i]=rnk[i];
		p=0;
		for(int i=1;i<=n;i++){
			if(cmp(sa[i],sa[i-1],w)){
				rnk[sa[i]]=p;
			}else{
				rnk[sa[i]]=++p;
			}
		}
		if(p==n) break;
	}
	for(int i=1,k=0;i<=n;i++){
		if(rnk[i]==0) continue;
		if(k) k--;
		while(s[i+k]==s[sa[rnk[i]-1]+k]) k++;
		height[rnk[i]]=k;
	}
}
//ll tr[N];
int ne[N];
ll st[N],tt=-1;
ll res[N];
int qr(int l,int r){
	int res=1,len=0;
	while((res<<1)<r-l+1) res<<=1,len++;
	return max(ST[l][len],ST[r-res+1][len]);
}

int gao(int x,int val){
    if(x>n||qr(x,n)<=val) return n+1;
    int l=x,r=n;
    while(l<r){
        int mid=l+r>>1;
        if(qr(x,mid)>val) r=mid;
        else l=mid+1;
    }
    return l;
}

void __(){
    tt=0;
	scanf("%lld",&n);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	a[n+1]=1e9;
	vector<int> sg;
	for(int i=1;i<=n;i++) sg.push_back(a[i]);
	sort(sg.begin(),sg.end());
	sg.erase(unique(sg.begin(),sg.end()),sg.end());
	for(int i=1;i<=n;i++){
		aa[i]=lower_bound(sg.begin(),sg.end(),a[i])-sg.begin()+1;
		//		cout<<aa[i]<<" ";
	}
	getsa(aa);
	bool flag=0;
	tt=0;
	st[0]=n+1;
	
	for(int i=1;i<=n+1;i++) ST[i][0]=a[i];
// 	cout<<(1<<16)<<endl;
	for(int i=1;i<20;i++){
		for(int j=1;j<=n+1;j++){
			
			ST[j][i]=ST[j][i-1];
			if(j+(1<<(i-1))<=n) ST[j][i]=max(ST[j][i],ST[j+(1<<(i-1))][i-1]);
		}
	}
	ll ans=0;
	ll tot=0;
	st[0]=n+1;
	res[n+1]=0;
	for(int i=n;i>=1;i--){
	    int ne=gao(i+1,a[i]);
	    res[i]=res[ne]+(ne-i)*a[i];
	    //cout<<res[i]<<" "<<res[st[tt]]<<endl;
	}
// 	cout<<endl;
	for(int i=n;i>=1;i--){
	    ll ht=height[rnk[i]];
	    if(ht==0){
	        ans+=res[i];
	        continue;
	    }
	    int mx=qr(i,i+ht-1);
	    int j=gao(i+ht,mx);
	    int ii=i+ht;
	    
	    ans+=(j-ii)*mx+res[j];
	    
	}
	for(int i=0;i<=(n<<1);i++){
		sa[i]=0,height[i]=0,rnk[i]=0,id[i]=0,oldrnk[i]=0,key1[i]=0,cnt[i]=0;
		for(int j=0;j<20;j++) ST[i][j]=0;
		res[i]=0;
		aa[i]=0;
	}
	printf("%lld\n",ans);
}

signed main(){
	int _;
	cin>>_;
	while(_--){
		__();
// 		if(_==400) cout<<n<<endl; 
	}
	
}