#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
mt19937 rnd(time(0));
const int MAXN=2e5+5;
const int MOD=1e9+7;
int n,a[MAXN];
ll hs[MAXN],pw[MAXN],tot,P=rnd()%MOD;
ll get_hs(ll l,ll r){return (hs[r]-pw[r-l+1]*hs[l-1]%MOD+MOD)%MOD;}
ll change(int l,int r,int x,int c){
	if(x<l||x>r) return 0;
	return (c-a[x]+MOD)*pw[r-x]%MOD;
}
unordered_map<int,ll> mp[MAXN];
ll s0[MAXN],s1[MAXN];
void solve(){
	cin>>n;
	tot=n;
	for(int i=1;i<=n;i++){
		mp[i].clear();
		s0[i]=s1[i]=0;
	}
	for(int i=1;i<=n;i++) cin>>a[i],hs[i]=(hs[i-1]*P+a[i])%MOD;
	for(int i=2;i<=n;i++){
		int l=i-1,r=n,mid;
		while(l<r){
			mid=l+r+1>>1;
			if(get_hs(i,mid)==get_hs(1,mid-i+1)) l=mid;
			else r=mid-1;
		}
		tot+=l-i+1;
		// [i,l] += (l+1-x)
		s0[i]+=l+1;s0[l+1]-=l+1;
		s1[i]--;s1[l+1]++;
		// [1,l+1-i] += (l+2-i-j)
		if(l+1-i<i){
			s0[1]+=l+2-i;s0[l+2-i]-=l+2-i;
			s1[1]--;s1[l+2-i]++;
		}else{
			s0[1]+=l+2-i;s0[i]-=l+2-i;
			s1[1]--;s1[i]++;
		}
		if(l!=n){
			int j=l+1,p=j-i+1;
			l=j,r=n;
			while(l<r){
				mid=l+r+1>>1;
				if(get_hs(j+1,mid)==(get_hs(p+1,mid-j+p)+change(p+1,mid-j+p,j,a[p]))%MOD) l=mid;
				else r=mid-1;
			}
			mp[j][a[p]]+=l-j+1;
			l=j,r=n;
			while(l<r){
				mid=l+r+1>>1;
				if(get_hs(j+1,mid)==get_hs(p+1,mid-j+p)) l=mid;
				else r=mid-1;
			}
			mp[p][a[j]]+=l-j+1;
		}
	}
	ll res=0;
	for(int i=1;i<=n;i++){
		s0[i]+=s0[i-1];s1[i]+=s1[i-1];
		ll ans=0;
		for(auto j:mp[i]) ans=max(ans,j.second);
		res+=(tot-(s0[i]+i*s1[i])+ans)^i;
	}
	cout<<res<<'\n';
	return;

}
int main(){
	ios::sync_with_stdio(false);
	// freopen("Otomachi_Una.in","r",stdin);
	// freopen("Otomachi_Una.out","w",stdout);
	pw[0]=1;
	for(int i=1;i<MAXN;i++) pw[i]=pw[i-1]*P%MOD;
	int _;cin>>_;
	while(_--) solve();
	return 0;
}