#include<bits/stdc++.h>
#define ll long long
#define ssz(x) ((int)x.size())
using namespace std;
const int N=3e5+5;
int n,m;
inline int red(){
	int data=0;bool w=0;char ch=getchar();
	while(ch!='-' && (ch<'0' || ch>'9'))ch=getchar();
	if(ch=='-') w=1,ch=getchar();
	while(ch>='0' && ch<='9') data=(data<<3)+(data<<1)+ch-'0',ch=getchar();
	return w?-data:data;
}
struct Hash{
	ll hs[N],pw[N],seed,Mod;
	void init(int *A,int n,ll sd,ll md){
		pw[0]=1;
		seed=sd;
		Mod=md;
		for(int i=1;i<=n;i++){
			pw[i]=pw[i-1]*seed%Mod;
			hs[i]=(hs[i-1]*seed%Mod+A[i])%Mod;
		}
	}
	ll get(int l,int r){
		if(l>r) return 0;
		ll now=(hs[r]-hs[l-1]*pw[r-l+1]%Mod)%Mod;
		if(now<0)now+=Mod;
		return now;
	}
}hs1,hs2;
int S[N];
int zf[N];
int zexpand(int *s,int arr1,int arr2,int n){
	while(arr2+1<n&&s[arr1+1]==s[arr2+1]){
		arr1++;arr2++;
	}
	return arr2;
}
void zfct(int *s,int n){
	int i,l=0,r=0;
	for(i=1;i<n;i++){
		if(i>r){
			zf[i]=zexpand(s,-1,i-1,n)-i+1;
			if(zf[i]+i-1>r) {
				l=i;
				r=zf[i]+i-1;
			}
		}else{
			if(zf[i-l]<r-i+1) zf[i]=zf[i-l];
			else{
				zf[i]=zexpand(s,r-i,r,n)-i+1;
				if(zf[i]+i-1>r){
					l=i;
					r=zf[i]+i-1;
				}
			}
		}
	}
}
int Z[N];
vector <int> vec[N];
//vector <pair<int,int>> veci[N<<1];
vector <int> veci[N<<1];
bool check(int l1,int r1,int l2,int r2){
	if(r2>n) return 0;
	int f1=(hs1.get(l1,r1)==hs1.get(l2,r2));
	int f2=(hs2.get(l1,r1)==hs2.get(l2,r2));
	return f1&&f2;
}
int lcp(int l1,int r1,int l2,int r2){
	if(r1<l1||r2<l2) return 0;
	r1=min(r1,n);
	r2=min(r2,n);
	int L=0,R=min(r1-l1+1,r2-l2+1);
	while(L<R){
		int mid=(L+R+1)>>1;
		int f1=(hs1.get(l1,l1+mid-1)==hs1.get(l2,l2+mid-1));
		int f2=(hs2.get(l1,l1+mid-1)==hs2.get(l2,l2+mid-1));
		if(f1&&f2){
			L=mid;
		}else{
			R=mid-1;
		}
	}
	return L;
}
ll fans[N];
void solve(){
	scanf("%d",&n);
	zf[0]=0;
	vec[0].clear();
	veci[0].clear();
	for(int i=1;i<=n;i++){
		vec[i].clear();
		veci[i].clear();
		veci[i+n].clear();
		zf[i]=0; fans[i]=0;
		scanf("%d",&S[i]);
	}
	hs1.init(S,n,2e5+5,1e9+7);
	hs2.init(S,n,2e5+5,1e9+9);
	zfct(S+1,n);
	for(int i=0;i<n;i++){
		Z[i+1]=zf[i];
	}
    Z[1] = n;
	ll total=0;
	for(int i=1;i<=n;i++){
		total+=Z[i];
		vec[Z[i]+1].push_back(i);
		veci[Z[i]+i].push_back(i);
//		printf("%d ",Z[i]);
	}
//	for(int i=1;i<=n;i++){
//		for(int j=i;j<=n;j++){
//			for(int k=1;k<=n;k++){
//				for(int w=k;w<=n;w++){
//					printf("%d~%d %d~%d: %d\n",i,j,k,w,lcp(i,j,k,w));
//				}
//			}
//		}
//	}
	ll x=n,sum=0,ls=0,ls2=0;
	ll sum1=0,sum2=0,x1=0,totans=0;
	map <int,ll> mp;
	for(int i=1;i<=n;i++){
        mp.clear();
		x-=ssz(vec[i]);
		if(Z[i]+1>i) x--;
		ls=0;
		if(Z[i]+1<i) sum-=Z[i];
		for(auto j:vec[i]){
		    //printf("vec see: %lld %lld nowsum: %lld\n",j,Z[j],sum);
		    if(j==1) continue;
			if(i<j){
				ls+=Z[j]; fans[i] += Z[j];
				//printf("add basic1: %lld %lld\n",Z[j],fans[i]);
				if(j+i-1 > n) continue;
				int now=lcp(i+1,n,j+i,n)+1;
				//printf("vec j: %lld %lld %lld\n",j,S[i+j-1],now);
				mp[S[i+j-1]]+=now;
			}
		}
        if(i!=1 && Z[i]+i>i){
            x1++;
            sum1+=i;
        }
		ls2=0;
		for(auto j:veci[i]){
			if(j<=i){
				ls2+=Z[j];
				if(j!=i) sum1-=j,x1--;
				fans[i] += Z[j];
				//printf("%lld add basic2: %lld %lld\n",j,Z[j],fans[i]);
                if(j==1) continue;
                int pos=i-j+1;
                if(check(pos+1,i-1,i+1,2*i-pos-1)){
                    if(2*i-pos<=n&&S[pos]==S[2*i-pos]){
                        int now=lcp(i+1,n,2*i-pos+1,n)+(i-pos)+1;
                        //printf("veci j: %lld %lld %lld----tp1\n",j,S[pos],now);
                        mp[S[pos]]+=now;
                    }else{
                        //printf("veci j: %lld %lld %lld----tp2\n",j,S[pos],i-pos-1);
                        mp[S[pos]]+=i-pos;
                    }
                }else{
                    int now=lcp(pos+1,i-1,i+1,2*i-pos-1)+1;
                    //printf("veci j: %lld %lld %lld----tp3\n",j,S[pos],now);
                    mp[S[pos]]+=now;
                }
			}
		}
		ll maxv=0,maxidx=0;
		//printf("---------------------now mpsiz: %d\n",ssz(mp));
		for(auto v:mp){
            if(v.second >= maxv)
            {
                maxv = v.second;
                maxidx = v.first;
            }
		}
		fans[i] += x1*i-sum1+sum2+maxv+x*(i-1)+sum;
		fans[i] += n;
		//printf("%lld %lld %lld %lld %lld %lld id: %lld %lld\n",x,sum,sum1,x1,sum2,maxv,maxidx,fans[i]);
		totans+=(fans[i]^i);
		sum+=ls;
		sum2+=ls2;
	}
	printf("%lld\n",totans);
//	printf(" Total: %lld\n",total);
}
int main()
{
	//ios::sync_with_stdio(false);
	//cin.tie(0);
	//cout.tie(0);
	int T=1;
	T=red();
	while(T--)solve();
	return 0;
}