#include <bits/stdc++.h>
#define rint int
using namespace std;
const int maxn = 1000005;
int LOG[maxn];
int sa[maxn];
int bar[maxn];
int fir[maxn];
int sec[maxn<<1];
int rk[maxn];
int hei[maxn];
int s[maxn];
int pre[maxn];
int lsh[maxn];
int nxt[maxn];
int sta[maxn];
int n,m, sss[maxn];

int top, stk[maxn];
long long sum[maxn];
int st[maxn][21];

void qsort()
{
	memset(bar,0,m+1<<2);
	for(rint i=1;i<=n;i++) bar[fir[i]]++;
	for(rint i=1;i<=m;i++) bar[i]+=bar[i-1];
	for(rint i=n;i>=1;i--) sa[bar[fir[sec[i]]]--]=sec[i];
}

void get_sa()
{
	for(rint i=1;i<=n;i++) fir[i]=s[i],sec[i]=i;
	qsort();
	for(rint k=1;;k<<=1)
	{
		rint num=0;
		for(rint i=1;i<=k;i++) sec[++num]=n-k+i;
		for(rint i=1;i<=n;i++) if(sa[i]>k) sec[++num]=sa[i]-k;
		qsort();
		memcpy(sec,fir,sizeof(fir));
		fir[sa[1]]=m=1;
		for(rint i=2;i<=n;i++)
			fir[sa[i]]=sec[sa[i]]==sec[sa[i-1]]&&sec[sa[i]+k]==sec[sa[i-1]+k]?m:++m;
		if(m==n) return;
	}
}

void get_hei()
{
	for(rint i=1;i<=n;i++) rk[sa[i]]=i;
	for(rint i=1,k=0;i<=n;i++)
	{
		if(k) k--;
		rint j=sa[rk[i]-1];
		while(s[i+k]==s[j+k]) k++;
		hei[rk[i]]=k;
	}
	
	for (int i = 1; i <= n; ++i)
		st[i][0] = hei[i];
	for (int j = 1; j <= 20; ++j)
		for (int i = 1; i <= n; ++i)
			st[i][j] = min(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
}

int get_lcp(int x, int y) {
	int len = LOG[y - x + 1];
	return min(st[x][len], st[y - (1 << len) + 1][len]);
}

int main() {
	LOG[0] = -1;
	for (int i = 1; i <= 1000000; ++i) LOG[i] = LOG[i >> 1] + 1;
	int T;
	cin >> T;
	while (T--) {
		scanf("%d", &n);
		for (int i = 1; i <= n; ++i) {
			scanf("%d", &s[i]);
			lsh[i]=s[i];
			sss[i] = s[i];
		}
		sort(lsh+1,lsh+n+1);
		m=unique(lsh+1,lsh+n+1)-lsh-1;
		for(rint i=1;i<=n;i++)
			s[i]=lower_bound(lsh+1,lsh+m+1,s[i])-lsh;
		get_sa(),get_hei();
		for (int i = 1; i <= n; ++i) s[i] = sss[i];
		int top = 0;
		stk[0] = n + 1;
		for (int i = n; i >= 1; --i) {
			while (top && s[i] >= s[stk[top]]) --top;
			stk[++top] = i;
			sum[top] = sum[top - 1] + 1ll * s[i] * (stk[top - 1] - i);
		}
		
		set<int> ss;
		long long ans = 0;
		for (int i = n; i >= 1; --i) {
			int lcp = 0;
			auto up = ss.upper_bound(rk[i]);
			if (up != ss.end()) lcp = max(lcp, get_lcp(rk[i] + 1, *up));
			if (up != ss.begin()) --up, lcp = max(lcp, get_lcp(*up + 1, rk[i]));
			ss.insert(rk[i]);
			
			int idx = lower_bound(stk + 1, stk + top + 1, i + lcp, greater<int>()) - stk;
			ans += sum[idx - 1] + 1ll * s[i] * (stk[idx - 1] - i - lcp);
		}
		cout << ans << endl;
	}
	return 0;
}