#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define int ll

const int N=2e5+5;

int n,m;
ll a[N],s[N];

vector<int> sa,rk;

vector<int> h;//h[i]=lcp(sa[i],sa[i-1]);

//s下标从1开始
void init(){
    
    vector<int> cnt(max(n+1,m+1)),oldrk(2*n+1),id(n+1),key(n+1);
    sa.resize(n+1);rk.resize(n+1);
    for(int i=0;i<=n;i++) sa[i]=rk[i]=0;
    
    auto cmp=[&](int x,int y,int w){
        return oldrk[x]==oldrk[y]&&oldrk[x+w]==oldrk[y+w];
    };

    for(int i=1;i<=n;i++)++cnt[rk[i]=s[i]];
    for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
    for(int i=n;i>=1;i--)sa[cnt[rk[i]]--]=i;

    for(ll w=1;;w<<=1){
        int 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;
        fill(cnt.begin(),cnt.end(),0);
        for(int i=1;i<=n;i++)++cnt[key[i]=rk[id[i]]];

        for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
        for(int i=n;i>=1;i--)sa[cnt[key[i]]--]=id[i];
        copy(rk.begin()+1,rk.end(),oldrk.begin()+1);
        p=0;
        for(int i=1;i<=n;i++)rk[sa[i]]=cmp(sa[i],sa[i-1],w)?p:++p;
        if(p==n)break;
        m=p;
    }

    for(int i=1,k=0;i<=n;i++){
        if(rk[i]==0)continue;
        if(k)--k;
        while(s[i+k]==s[sa[rk[i]-1]+k])++k;
        h[rk[i]]=k;
    }


}


array<ll,3> sta[N];
int top;
ll sum[N];
ll ans;



void solve(){
    cin>>n;
    h.resize(n+1);
    for(int i=0;i<=n;i++) h[i]=0;

    vector<int> tmp;

    m=0;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        tmp.push_back(s[i]);
        a[i]=s[i];
    }
    ans=top=0;

    sort(tmp.begin(),tmp.end());
    tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());
    for(int i=1;i<=n;i++){
        s[i]=lower_bound(tmp.begin(),tmp.end(),s[i])-tmp.begin()+1;
    }
    m=tmp.size()+10;

    init();

    for(int i=n;i>=1;i--){
        while(top&&a[i]>sta[top][0]){
            top--;
        }
        ll val=n-i+1;
        if(top) val=sta[top][1]-1-i+1;
        array<ll,3> arr;
        arr[0]=a[i],arr[1]=i,arr[2]=val;
        sta[++top]=arr;
        sum[top]=sum[top-1]+1ll*a[i]*val;

        int len=h[rk[i]];

        int l=1,r=top,mid,pos=-1;
        while(l<=r){
            mid=(l+r)>>1;
            if(sta[mid][1]-i+1>len){
                pos=mid;
                l=mid+1;
            }else r=mid-1;
        }

        // cout<<"! "<<len<<"\n";
        // for(int i=1;i<=top;i++) cout<<"@ "<<i<<" "<<sta[i][0]<<" "<<sta[i][1]<<" "<<sta[i][2]<<"\n";
        // cout<<"# "<<i<<" "<<pos<<" "<<len<<"\n";
        if(pos==-1){
            ans+=1ll*sta[1][0]*(1ll*(n-i+1)-len);
            continue;
        }

        ans+=sum[pos];
        // if(pos<top)
            ans+=1ll*sta[pos+1][0]*(1ll*(sta[pos][1]-1-i+1)-len);
        
        // cout<<ans<<"\n";

    }

    cout<<ans<<"\n";
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n=1;
    cin>>n;
    while(n--)solve();
    return 0;
}