/*
Things to notice:
1. do not calculate useless values
2. do not use similar names
 
Things to check:
1. submit the correct file
2. time (it is log^2 or log)
3. memory
4. prove your naive thoughts 
5. long long
6. corner case like n=0,1,inf or n=m
7. check if there is a mistake in the ds or other tools you use
8. fileio in some oi-contest

9. module on time 
10. the number of a same divisor in a math problem
11. multi-information and queries for dp and ds problems
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pii pair<long long,long long>
#define mp make_pair
#define pb push_back
int n,s[200005];
struct BIT
{
	int t[200005];
	void init()
	{
		for(int i=1;i<=n;i++) t[i]=0; 
	}
int lowbit(int x)
{
	return x&(-x);	
} 
void update(int x,int d)
{
	for(int i=x;i<=n;i+=lowbit(i)) t[i]+=d;
}
int query(int x)
{
	int res=0;
	for(int i=x;i>=1;i-=lowbit(i)) res+=t[i];
	return res;
}
}bt,bt2; 
int upd_pos,upd_val;
struct Hashing
{
	int mod,bse;
	int pw[200005];
	int H1[200005];
	void init(int M,int B)
	{
		mod=M,bse=B;
		pw[0]=1;
		for(int i=1;i<=n;i++) pw[i]=1LL*pw[i-1]*bse%mod;
		for(int i=1;i<=n;i++) H1[i]=1LL*bse*H1[i-1]%mod+(s[i]),H1[i]%=mod;
	}
	int query(int l,int r)
	{
		int re=(H1[r]-1LL*H1[l-1]*pw[r-l+1]%mod+mod)%mod;
		if(l<=upd_pos&&upd_pos<=r) 
		{
			int wei=r-upd_pos;
			re=(re-pw[wei]*s[upd_pos]%mod+mod)%mod;
			re=(re+pw[wei]*upd_val)%mod;
		}
		return re;
	}
}h1,h2;
int chkequ(int l1,int r1,int l2,int r2)
{
	if(h1.query(l1,r1)!=h1.query(l2,r2)) return 0;
	return h2.query(l1,r1)==h2.query(l2,r2);
}
int ans[200005];
vector <pii > buc[200005]; 
int getz(int x)
{
	int l=1,r=n-x+1,res=0;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(chkequ(1,mid,x,x+mid-1)) res=mid,l=mid+1;
		else r=mid-1;
	}
	return res;
}
void solve()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>s[i],ans[i]=0,buc[i].clear();
	h1.init(998244853,19260817);
	h2.init(1e9+7,1919810);
	bt.init();
	for(int i=2;i<=n;i++)
	{
		upd_pos=0;
		int res=getz(i);
		// case 1: outsize [1,z[i]] and [i,i+z[i]-1]
		if(res+1<=i-1) bt.update(res+1,res),bt.update(i,-res);
		if(i+res<=n) bt.update(i+res,res); 
		// case 2: i+z[i] or z[i]+1
		if(res<n-i+1)
		{
			int j=i+res+1;			
			upd_pos=j-1,upd_val=s[res+1];
			int res2=getz(i);
			buc[j-1].pb(mp(s[res+1],res2-res));
			
			
			if(res+1>=i) continue;
			upd_pos=res+1,upd_val=s[i+res];
			res2=getz(i);
			buc[res+1].pb(mp(s[i+res],res2-res));
		}
		
	}
	for(int i=1;i<=n;i++) ans[i]+=bt.query(i);//,cout<<ans[i]<<" ";
//	cout<<"\n";
	bt.init(),bt2.init();
	// case 3: in [i,i+z[i]-1]
	for(int i=2;i<=n;i++)
	{
		int res=getz(i);
		if(res)
		{
			bt.update(i,1),bt.update(i+res,-1);
			bt2.update(i,i),bt2.update(i+res,-i); 
		}
	}
	for(int i=1;i<=n;i++) ans[i]+=i*bt.query(i)-bt2.query(i);
	// case 4: in[1,z[i]]
	bt.init(),bt2.init();
	for(int i=2;i<=n;i++)
	{
		upd_pos=0;
		int res=getz(i);
		if(res<i)
		{
			bt.update(1,1),bt.update(res+1,-1);
			bt2.update(1,1),bt2.update(res+1,-1);
		}
		else
		{
			bt.update(1,1),bt.update(i,-1);
			bt2.update(1,1),bt2.update(i,-1);
		}
	}
	for(int i=1;i<=n;i++) ans[i]+=i*bt.query(i)-bt2.query(i);
//	for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
//	cout<<"\n";
	int Ans=0;
	
//	cout<<"\n";
	for(int i=1;i<=n;i++)
	{
		sort(buc[i].begin(),buc[i].end());
		int maxx=0;
		for(int j=0;j<buc[i].size();j++)
		{
			int k=j,res=0;
			while(k<buc[i].size()&&buc[i][k].fi==buc[i][j].fi) res+=buc[i][k].se,k++;
//			cout<<i<<": "<<buc[i][j].fi<<" "<<res<<"\n";
			k--,j=k;
			maxx=max(maxx,res);
		}
		ans[i]+=maxx+n;
		Ans+=(ans[i]^i);
//		cout<<i<<": "<<ans[i]<<"\n"; 
	}
	cout<<Ans<<"\n";
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int _=1;
	cin>>_;
	while(_--) solve();
	return 0;
}