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

const int N=2e5+10;
int n,f[N],z[N],s[N],d[N];
map<int,int> mp[N];

int lowbit(int x) {return x&-x;}
void add(int x,int v) {while (x<=n) f[x]+=v,x+=lowbit(x);}
int query(int x) {int ans=0; while (x>0) ans+=f[x],x-=lowbit(x); return ans;}
void update(int l,int r,int v) {add(l,v),add(r+1,-v);}

struct Bart{
	int I,m;
	void ini(int Mod) {m=Mod; I=(1ll<<62)/m;}
	int operator()(int x) {
		int tp=x-((__int128)x*I>>62)*m;
		while (tp>=m) tp-=m;
		while (tp<0) tp+=m;
		return tp;
	}
};
struct hash{
	int base,mod;
	Bart getmod;
	int p[N],h[N];
	void init(int Base,int Mod) {
		base=Base,mod=Mod; getmod.ini(mod); p[0]=1;
		for (int i=1;i<=n;i++) p[i]=getmod(p[i-1]*base);
		for (int i=1;i<=n;i++) h[i]=getmod(h[i-1]*base+(s[i]^114514));
	}
	int gethash(int l,int r,int pos,int u,int v) {
		int hash=getmod(h[r]-h[l-1]*p[r-l+1]);
		u=u^114514,v=v^114514;
		if (l<=pos&&pos<=r) {
			hash-=getmod(u*p[r-pos]); hash+=getmod(v*p[r-pos]);
			hash=getmod(hash);
		} return hash;
	}
}h[2];
bool equ(int l1,int r1,int l2,int r2,int pos,int u,int v) {
	return h[0].gethash(l1,r1,pos,u,v)==h[0].gethash(l2,r2,pos,u,v)&&h[1].gethash(l1,r1,pos,u,v)==h[1].gethash(l2,r2,pos,u,v);
}

void solve() {
	cin>>n;
	for (int i=1;i<=n;i++) cin>>s[i],f[i]=0;
	z[1]=n; h[0].init(402653189,1e9+7); h[1].init(998244353,1610612741);
	for (int i=2,l=0,r=0;i<=n;i++) {
		if (i<=r) z[i]=min(z[i-l+1],r-i+1); else z[i]=0;
		while (i+z[i]<=n&&s[i+z[i]]==s[z[i]+1]) ++z[i];
		if (i+z[i]-1>r) l=i,r=i+z[i]-1;
	}
	// for (int i=1;i<=n;i++) cout<<z[i]<<' '; cout<<'\n';
	int sum=0; for (int i=1;i<=n;i++) sum+=z[i];
	for (int i=2;i<=n;i++) {
		if (z[i]) {
			update(i,i,z[i]),update(i+1,i+z[i],-1);
			if (i<=z[i]) update(1,1,z[i]),update(2,i-1,-1),update(i,i,-z[i]+i-2);
			else update(1,1,z[i]),update(2,1+z[i],-1);
		}
		if (i+z[i]-1==n) continue;
		
		int v1=s[i+z[i]],v2=s[z[i]+1],lcp;
		
		s[z[i]+1]=v1;
		if (i+z[i]+1>n||s[z[i]+2]!=s[i+z[i]+1]) lcp=0;
		else {
			int l=0,r=n-(i+z[i]+1);
			int s1=z[i]+2,s2=i+z[i]+1;
			while (l<r) {
				int mid=r-((r-l)>>1);
				if (equ(s1,s1+mid,s2,s2+mid,z[i]+1,v2,v1)) l=mid;
				else r=mid-1;
			}
			lcp=l+1;
		}
		s[z[i]+1]=v2; mp[z[i]+1][v1]+=lcp+1;
		// cout<<z[i]+1<<' '<<v1<<' '<<lcp<<'\n';

		s[i+z[i]]=v2;
		if (i+z[i]+1>n||s[z[i]+2]!=s[i+z[i]+1]) lcp=0;
		else {
			int l=0,r=n-(i+z[i]+1);
			int s1=z[i]+2,s2=i+z[i]+1;
			while (l<r) {
				int mid=r-((r-l)>>1);
				if (equ(s1,s1+mid,s2,s2+mid,i+z[i],v1,v2)) l=mid;
				else r=mid-1;
			}
			lcp=l+1;
		}
		s[i+z[i]]=v1; mp[i+z[i]][v2]+=lcp+1;
	}
	for (int i=1;i<=n;i++) d[i]=d[i-1]+query(i);
	int ans=0;
	for (int i=1;i<=n;i++) {
		int mx=0;
		for (auto [c,v]:mp[i]) mx=max(mx,v); mp[i].clear();
		// cout<<mx<<' ';
		ans+=(sum+mx-d[i])^i;
	} cout<<ans<<'\n';
}

signed main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int T; cin>>T; while (T--) solve();
}