#include<bits/stdc++.h>
#define LB lower_bound
#define fi first
#define se second
using namespace std;using ll=long long;
const int N=2e5+5,mod=998244353;
int n,A[N];
namespace SA{
	ll sum[N];
	const int bas=998244353;
	const ll mod=ll(1e18)+31;
	using LL=__int128;
	ll pw[N];
	void build(){
		for(int i=1;i<=n;i++) sum[i]=(LL(sum[i-1])*bas+A[i])%mod;
		for(int i=pw[0]=1;i<=n;i++) pw[i]=LL(pw[i-1])*bas%mod;
	}
	LL qryHa(int x,int y){
		return (sum[y]+LL(mod-sum[x-1])*pw[y-x+1])%mod;
	}
	int LCP(int x,int y){
		int l=0,r=min(n-x+1,n-y+1)+1,mid;
		while(l+1<r) mid=l+r>>1,(qryHa(x,x+mid-1)==qryHa(y,y+mid-1)?l:r)=mid;
		return l;
	}
}
struct bit{
	ll f[N];
	void clr(){fill(f+1,f+n+1,0ll);}
	void add(int x,ll y){while(x<=n) f[x]+=y,x+=x&-x;}
	ll qry(int x){ll ans=0;while(x) ans+=f[x],x-=x&-x;return ans;}
}f1,f2,f3;
int len[N];
ll sum[N];
map<int,ll> f[N];
void Solve(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&A[i]);
	SA::build();
	for(int i=1;i<=n;i++) sum[i]=n;
	for(int i=2;i<=n;i++) len[i]=SA::LCP(1,i);
	f1.clr();f2.clr();
	for(int i=n;i;i--){
		sum[i]+=f1.qry(i-1)+(f2.qry(n)-f2.qry(i-1))*(i-1);
		if(len[i]){
			f1.add(len[i],len[i]);
			f2.add(len[i],1);
		}
	}
	// for(int i=1;i<=n;i++) cerr<<sum[i]<<' ';cerr<<'\n';
	f1.clr();f2.clr();f3.clr();
	for(int i=2;i<=n;i++){
		if(len[i]){
			f1.add(i+len[i]-1,len[i]);f2.add(i+len[i]-1,i-1);f3.add(i+len[i]-1,1);
		}
		sum[i]+=f1.qry(i-1)+(i-1)*(f3.qry(n)-f3.qry(i-1))-(f2.qry(n)-f2.qry(i-1));
	}
	for(int i=1;i<=n;i++) f[i].clear();
	for(int i=2;i<=n;i++) if(i+len[i]<=n){
		int w=len[i]+1+SA::LCP(i+len[i]+1,len[i]+2);
		if(w>=i+len[i]-1){
			if(A[i+(i+len[i])-1]==A[len[i]+1]){
				assert(w==i+len[i]-1);
				w+=1+SA::LCP(i+(i+len[i]),i+len[i]+1);
			}else w=i+len[i]-1;
		}
		f[i+len[i]][A[len[i]+1]]+=w-len[i];
		if(len[i]+1<i){
			f[len[i]+1][A[i+len[i]]]+=1+SA::LCP(len[i]+2,i+len[i]+1);
		}
	}
	ll tot=0;
	for(int i=1;i<=n;i++){
		ll mx=0;
		for(auto [u,v]:f[i]) mx=max(mx,v);
		tot+=(sum[i]+mx^i);
		// cerr<<sum[i]+mx<<'\n';
	}
	printf("%lld\n",tot);
}
int main(){
	int t=1;
	scanf("%d",&t);
	while(t--) Solve();
	return 0;
}