//#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define N 200005
#define mod 998244353
#define base 19491001
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define ls (rt<<1)
#define rs ((rt<<1)|1)
#define fi first
#define se second
#define INF 1e9
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
int qpow(int a,int b){
	int res=1;
	for(;b;b>>=1){
		if(b&1) res=res*a%mod;
		a=a*a%mod;
	}
	return res;
}
/*int fac[N],ifac[N];
int C(int n,int m){
	if(m>n||m<0||n<0) return 0;
	return fac[n]*ifac[n-m]%mod*ifac[m]%mod;
}
void init(){
	fac[0]=1;
	for(int i=1;i<N;i++) fac[i]=fac[i-1]*i%mod;
	ifac[N-1]=qpow(fac[N-1],mod-2);
	for(int i=N-2;i>=0;i--) ifac[i]=ifac[i+1]*(i+1)%mod;
}*/
inline int lowbit(int x){return x&(-x);}
inline int read(){
  int x=0,t=1;char ch=getchar();
  while(ch<'0'||ch>'9'){
    if(ch=='-') t=-1;
    ch=getchar();
  }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch-'0');
        ch=getchar();
    }
    return x*t;
}
inline void write(int x){
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
}
int T,n,z[N],a[N],p[N],ip[N],s[N],res[N],s1[N],s2[N],pos,to;
map<int,int>ma[N];
int qry(int l,int r){
	int res=(s[r]-s[l-1]+mod)*ip[l-1]%mod;
	if(pos>=l&&pos<=r){
		res=res-a[pos]*p[pos-l+1]+to*p[pos-l+1];
		res=(res%mod+mod)%mod;
	}
	return res;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;p[0]=1;
	for(int i=1;i<N;i++) p[i]=p[i-1]*base%mod;
	ip[N-1]=qpow(p[N-1],mod-2);
	for(int i=N-2;i>=0;i--) ip[i]=ip[i+1]*base%mod;
	while(T--){
		cin>>n;pos=0;to=0;
		for(int i=1;i<=n;i++) ma[i].clear(),z[i]=0,s1[i]=0,s2[i]=0;
		for(int i=1;i<=n;i++)
			cin>>a[i];
		for(int i=1;i<=n;i++){
			s[i]=s[i-1];
			(s[i]+=a[i]*p[i])%=mod;
		}
		z[1]=n;
		//还要考虑所有的都是特殊的情况 
		for(int i=2,l=0,r=0;i<=n;i++){
			if(r>=i) z[i]=min(i-l+1,z[r-i+1]);
			while(i+z[i]<=n&&a[z[i]+1]==a[i+z[i]]) z[i]++;
			if(i+z[i]-1>=r) r=i+z[i]-1,l=i;
		}
		int ans=0;
		for(int i=2;i<=n;i++){
			//考虑lcp[i] 
			//1，修改z[i]+1 2.修改i+z[i] 会造成特殊影响
			//[1,z[i]],[i,i+z[i]-1]
			//对于[1,lim-1]，修改j贡献是j-1
			//对于[i,i+z[i]-1]，修改j贡献是j-i 
			int lim=min(i,z[i]+1);
			s1[1]+=-1;s1[lim]-=-1;s2[1]++;s2[lim]--;
			s1[i]+=-i;s1[i+z[i]]+=i;s2[i]++;s2[i+z[i]]--;
			//z[i]+2~i-1,i+z[i]+1~n，贡献是z[i] 
			if(z[i]+2<=i-1) s1[z[i]+2]+=z[i],s1[i]-=z[i];
			if(i+z[i]+1<=n) s1[i+z[i]+1]+=z[i];
			if(i+z[i]==n+1){
				//z[i]+1答案+z[i]
				if(z[i]+1<i){
					s1[z[i]+1]+=z[i];
					s1[z[i]+2]-=z[i];
				}
				continue; 
			}
			//特殊考虑z[i]+1和i+z[i] 
			if(z[i]+1<i){
				s1[z[i]+1]+=z[i];
				s1[z[i]+2]-=z[i];
				//z[i]+1改成和i+z[i]相同，则会产生新lcp-z[i]贡献
				pos=z[i]+1;to=a[i+z[i]];
				int l=1,r=n-i+1,ans=0;
				while(l<=r){
					int mid=(l+r)>>1;
					if(qry(1,mid)==qry(i,i+mid-1)) ans=mid,l=mid+1;
					else r=mid-1;
				}pos=0;to=0;
				ma[z[i]+1][a[i+z[i]]]+=ans-z[i];
			}
			if(i+z[i]<=n){
				s1[i+z[i]]+=z[i];int res=0,l=1,r=n-i+1;
				s1[i+z[i]+1]-=z[i];pos=i+z[i];to=a[z[i]+1];
				while(l<=r){
					int mid=(l+r)>>1;
					if(qry(1,mid)==qry(i,i+mid-1)) res=mid,l=mid+1;
					else r=mid-1;
				}
				//cout<<i<<"+"<<res<<endl;
				pos=0;to=0;ma[i+z[i]][a[z[i]+1]]+=res-z[i];
				//i+z[i]和z[i]+1一样，注意qry的时候 
			}
		}
		for(int i=1;i<=n;i++) s1[i]+=s1[i-1],s2[i]+=s2[i-1];
		for(int i=1;i<=n;i++){
			int tmp=-INF;
			if(ma[i].empty()) tmp=0;
			else for(auto t:ma[i]) tmp=max(tmp,t.se);
			assert(tmp>=0);
			tmp=tmp+s1[i]+s2[i]*i;
			tmp=tmp+n;//cout<<i<<"+"<<tmp<<endl;
			ans+=(tmp^i);
		}
		cout<<ans<<endl;
	} 
	return 0;
}