#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
	if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
	if(x > y) x = y;
}

inline int popcnt(int x){
	return __builtin_popcount(x);
}

inline int ctz(int x){
	return __builtin_ctz(x);
}


/*ll power(ll p,int k = mod - 2){
	ll ans = 1;
	while(k){
		if(k % 2 == 1) ans = ans * p % mod;
		p = p * p % mod;
		k /= 2;	
	}
	return ans;
}*/
int T,n;
int str[200005];

int rk[200005],sa[200005],buc[200005],id[200005],pid[200005],ord[400005],h[200005],ST[20][200005];
inline int cmp(int x,int y,int len){
	return ord[x] != ord[y] || ord[x + len] != ord[y + len];
}
inline int qry(int l,int r){
	int x = __lg(r - l + 1);
	return min(ST[x][l],ST[x][r - (1 << x) + 1]);
}
inline int lcp(int x,int y){
	if(max(x,y) > n) return 0;
	if(x == y) return n - x + 1;
	x = rk[x];y = rk[y];
	if(x > y) swap(x,y);
	return qry(x + 1,y);
}

/*int lcp(int x,int y){
	int k = 0;
	while(x + k <= n && y + k <= n && str[x + k] == str[y + k]) k++;
	return k;
}*/

void init(){
	int m = n;
	fill(buc,buc + n + 1,0);
	rep(i,1,n) buc[str[i]]++;
	rep(i,1,m) buc[i] += buc[i - 1];
	rep(i,1,n) sa[buc[str[i]]--] = i;

	m = 0;
	rep(i,1,n){
		if(i == 1 || str[sa[i]] != str[sa[i - 1]]) m++;
		rk[sa[i]] = m;
	}

	for(int len = 1;len <= n;len *= 2){
		int cnt = 0;
		rep(i,n - len + 1,n) id[++cnt] = i;
		rep(i,1,n) if(sa[i] > len) id[++cnt] = sa[i] - len;
		fill(buc,buc + m + 1,0);
		rep(i,1,n) buc[pid[i] = rk[id[i]]]++;
		rep(i,1,m) buc[i] += buc[i - 1];
		per(i,n,1) sa[buc[pid[i]]--] = id[i];
		copy(rk,rk + n + 1,ord);
		m = 0;
		rep(i,1,n){
			if(i == 1 || cmp(sa[i],sa[i - 1],len)) m++;
			rk[sa[i]] = m;
		}
		if(m == n) break;
	}

	int k = 0;
	rep(i,1,n){
		if(k) k--;

		if(rk[i] == 1) continue;
		int j = sa[rk[i] - 1];
		while(i + k <= n && j + k <= n && str[i + k] == str[j + k]) k++;
		h[rk[i]] = k;
	}
	rep(i,1,n) ST[0][i] = h[i];
	rep(i,1,17){
		rep(j,1,n){
			if(j + (1 << i) - 1 > n) break;
			ST[i][j] = min(ST[i - 1][j],ST[i - 1][j + (1 << (i - 1))]);
		}
	}
}

ll result[200005];
map <int,ll> ans[200005];
void upd(int x,int y,int z){
//	printf("if %d set to %d add %d\n",x,y,z);
	ans[x][y] += z;
}

void solve(){
	scanf("%d",&n);
	rep(i,1,n){
		scanf("%d",&str[i]);
		result[i] = 0;
		ans[i].clear();
	}
	rep(i,1,3) str[n + i] = 0;
	init();

	rep(i,2,n){
		int sz = lcp(1,i);
//		printf("now i=%d\n",i);
		if(sz < i - 1){
			rep(k,1,i - 1) result[k] += min(k - 1,sz);
			if(i + sz <= n) upd(sz + 1,str[i + sz],1 + lcp(sz + 2,i + sz + 1));
		}else{
			rep(k,1,i - 1) result[k] += k - 1;
		}

		rep(k,i,n) result[k] += min(k - i,sz);
		if(i + sz > n) continue;

		int awa = lcp(2 + sz,i + 1 + sz);
		if(awa < i - 2){
			upd(i + sz,str[1 + sz],1 + awa);
			continue;
		}
		if(str[1 + sz] != str[i + i - 1 + sz]){
			upd(i + sz,str[1 + sz],i - 1);
			continue;			
		}
		upd(i + sz,str[1 + sz],i + lcp(i + 1 + sz,i + i + sz));;
	}

//	rep(i,1,n) printf("%lld ",result[i]);
//	printf("\n");
	ll Mx,output = 0;
	rep(i,1,n){
		Mx = 0;
		for(pair<int,ll> I:ans[i]) if(I.first != str[i]) chkmax(Mx,I.second);
		output += (Mx + result[i] + n) ^ i;
//		printf("%lld ",Mx + result[i] + n);
	}
	printf("%lld\n",output);
}

int main(){
//	freopen("test.in","r",stdin);
	scanf("%d",&T);
	while(T--) solve();
	return 0;
}