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

const int N=200050;

int a[N];

int b[N];
ll Brute(int x,int n){
	ll ans=0;
	for(int newChar=1;newChar<=n;newChar++){
		if(newChar==a[x])continue;
		for(int i=1;i<=n;i++)b[i]=a[i];
		b[x]=newChar;
		ll now=0;
		for(int i=1;i<=n;i++){
			int j=0;
			while(i+j<=n && b[1+j]==b[i+j])j++;
			now+=j;
		}
		ans=max(ans,now);
	}
	return ans;
}

int sa[N],id[N],lcp[N];
array<int,3> tmp[N];

void BuildSA(int n){
	for(int i=1;i<=n;i++)id[i]=a[i];
	for(int j=1;;j<<=1){
		for(int i=1;i<=n;i++){
			tmp[i]={id[i],i+j<=n?id[i+j]:n+1,i};
		}
		sort(tmp+1,tmp+1+n);
		int c=0;
		for(int i=1;i<=n;i++){
			id[tmp[i][2]]=c+1;
			if(i==n || !(tmp[i][0]==tmp[i+1][0] && tmp[i][1]==tmp[i+1][1]))c++;
		}
		if(c==n)break;
	}
	for(int i=1;i<=n;i++)sa[id[i]]=i;
}

void BuildLCP(int n){
	int k=0;
	for(int i=1;i<=n;i++){
		if(id[i]!=n){
			int other=sa[id[i]+1];
			while(max(other,i)+k<=n && a[other+k]==a[i+k])k++;
			lcp[id[i]]=k;
		}
		if(k>0)k--;
	}
}

const int L=20;
int rmq[N][L],logs[N];
void BuildST(int n){
	for(int i=2;i<=n;i++)logs[i]=logs[i>>1]+1;
	for(int i=1;i<=n;i++)rmq[i][0]=lcp[i];
	for(int j=1;j<L;j++){
		for(int i=1;i<=n-(1<<j)+1;i++){
			rmq[i][j]=min(rmq[i][j-1],rmq[i+(1<<(j-1))][j-1]);
		}
	}
}

int LCP(int a,int b,int n){
	int l=id[a];
	int r=id[b];
	if(l>r)swap(l,r);
	if(l==r)return n-l+1;
	int k=logs[r-l];
	return min(rmq[l][k],rmq[r-(1<<k)][k]);
}

int R[N],len[N];
vector<int> endsHere[N],loHere[N];
int main(){
	int t;
	scanf("%i",&t);
	while(t--){
		int n;
		scanf("%i",&n);
		for(int i=1;i<=n;i++)scanf("%i",&a[i]);
		a[n+1]=n+1;
		BuildSA(n+1);
		BuildLCP(n+1);
		BuildST(n+1);

		ll sumL=0;
		int cntR=0;
		ll sumR=0;
		for(int i=2;i<=n;i++){
			len[i]=LCP(1,i,n);
			R[i]=i+len[i];
			if(R[i]<=n){
				sumL+=len[i];
				endsHere[R[i]].pb(i);
			}else{
				cntR++;
				sumR+=i;
			}
			loHere[min(len[i]+1,i)].pb(i);
		}

		ll sumLo=0;
		int cntHi=0;

		ll sol=0;
		for(int i=n;i>=1;i--){
			ll ans=sumL;
			//printf("sumL %lld\n",sumL);
			ans+=(ll)cntR*i-sumR;
			//printf("sumR %lld (%i)\n",(ll)cntR*i-sumR,cntR);
			ans+=n;

			ans+=sumLo;
			//printf("sumLo %lld\n",sumLo);
			ans+=cntHi*(i-1);
			//printf("sumHi %lld (%i)\n",cntHi*(i-1),cntHi);

			map<int,ll> best;
			for(int j:endsHere[i]){
				int newChar=a[len[j]+1];

				int lcp=len[j]+1+min(LCP(j+len[j]+1,len[j]+2,n),i-1-len[j]-1);
				if(lcp==i-1){
					if(newChar==a[j+lcp]){
						lcp++;
						lcp+=LCP(len[j]+2,j+lcp,n);
					}
				}
				//printf("[E]: Change to %i -> %i new lcp %lld\n",newChar,j,lcp);
				best[newChar]+=lcp-len[j];
			}

			for(int j:loHere[i]){
				if(len[j]==i-1 && j+i<=n){
					int newChar=a[j+i-1];
					int lcp=len[j]+1+LCP(i+1,j+i,n);
					//printf("[L]: Change to %i -> %i new lcp %lld\n",newChar,j,lcp);
					best[newChar]+=lcp-len[j];
				}
			}

			if(best.size()){
				ll mx=best.begin()->second;
				for(auto p:best){
					//printf("Add %lld for char %i\n",p.second,p.first);
					mx=max(mx,p.second);
				}
				ans+=mx;
			}

			//printf("i=%i ans=%lld brute=%lld\n",i,ans,Brute(i,n));
			sol+=ans^i;

			for(int j:endsHere[i]){
				sumL-=len[j];
				sumR+=j;
			}
			cntR+=endsHere[i].size();

			sumR-=i;
			cntR--;

			sumLo+=len[i];
			for(int j:loHere[i]){
				sumLo-=len[j];
				cntHi++;
			}
		}
		printf("%lld\n",sol);

		for(int i=1;i<=n;i++){
			endsHere[i].clear();
			loHere[i].clear();
		}
	}
	return 0;
}