#include<bits/stdc++.h>
using namespace std;
#define double long double
#define lowbit(x) (x&(-x))
#define int long long
#define ull unsigned long long
const pair<ull,ull>base = {19260817,1000000009};
int p[200005];
int n;
int a[200005]; 
int k[200005],b[200005],c[200005];
int ans[200005];
//答案表示为 ki+b 
int r[200005],pos[200005],rr[200005];
pair<ull,ull> pre[200005],pw[200005];
vector<pair<int,int> >s[200005];
//从 i 位置开始匹配能到哪里
//第一个不一样的位置
//不考虑第一个不一样的位置后能匹配到哪里 
pair<ull,ull> operator*(pair<ull,ull>x,pair<ull,ull> p){
	auto y=x;y.first*=p.first,y.second*=p.second;return y;
}
pair<ull,ull> operator+(pair<ull,ull>x,pair<ull,ull>p){
	auto y = x;y.first+=p.first,y.second+=p.second;return y;
}
pair<ull,ull> operator-(pair<ull,ull>x,pair<ull,ull>p){
	auto y = x;y.first-=p.first,y.second-=p.second;return y;
}
pair<ull,ull> calc(int l,int r,int pos =0){
	if(l>r)return {0,0};
	if(!pos)return pre[r]-pre[l-1]*pw[r-l+1];
	if(l<=pos and pos<=r){
		auto x1 = calc(l,pos-1),x2 = calc(pos+1,r);
		auto x = (x1*base+(pair<ull,ull>){a[pos],a[pos]})*pw[r-pos]+x2;
		return x;
	}
	return calc(l,r);
}
void add(int l,int r,int K,int C,int id){
	if(l>r)return;
//	if(l<=3 and r>=3)cout << l << " " << r << " " << id << " " << K << " " << C << endl; 
	k[l]+=K,k[r+1]-=K;
	c[l]+=C,c[r+1]-=C;
}
int query(int pos,int c,int i){
	int l  =i,r = n;
//	cout << " " << pos << " " << c << " " << i << endl;
	swap(a[pos],c);
//	cout << a[pos] << endl;
	while(l<r){
		int mid = l+r+1>>1;
		int len = mid-i+1;
//		cout << len << " " << calc(1,len,pos) << " " << calc(i,mid,pos) << endl;
		if(calc(1,len,pos) == calc(i,mid,pos))l = mid;
		else r = mid-1;
	}
	swap(a[pos],c);
	return l;
}
void solve(){
	cin >> n;
	for(int i = 1;i<=n;i++)p[i] = i;random_shuffle(p+1,p+1+n);
	for(int i = 1;i<=n;i++)cin >> a[i];
	for(int i = 1;i<=n;i++)a[i] = p[a[i]];
	for(int i =0;i<=n+1;i++)s[i].clear(),k[i]=b[i]=c[i]=0; 
	for(int i = 1;i<=n;i++)pre[i] = pre[i-1]*base+(pair<ull,ull>){1ull*a[i],1ull*a[i]};
	r[1]=n,pos[1]=n+1,rr[1]=n;
	for(int i = 2;i<=n;i++){
		int* xx = r;
		int l = 0,r = n-i+1;
		while(l<r){
			int mid = l+r+1>>1;
			if(calc(1,mid) == calc(i,i+mid-1)){
				l = mid;
			}else r = mid-1;
		}
		xx[i] = i+l-1;
	//	cout << " " << r;
		pos[i] = i+l;
		if(pos[i]>=n){
			rr[i] = n;
			continue;
		}
//		cout << "  " << pos[i] << " " << a[l+1] << endl;
		rr[i] = query(pos[i],a[l+1],i);
	}
//	cout << endl;
//	for(int i = 1;i<=n;i++)cout << r[i] << " ";cout << endl;
	c[1]=n;
//	for(int i = 1;i<=n;i++)cout << "  " << r[i] << " " << pos[i] << " " << rr[i] << endl;
	for(int i = 2;i<=n;i++){
		//如果在前面改则原串有可能发生变化
		// [L,R]
		// 在 [1,R-L+1] 改一个 
		// 如果 R-L+1>=R 则后面的串也会被改
		// 对 1 特判
		// 然后就是在 [1,min(L-1,R-L+1)] 改一个，贡献是 i-1 
		// 在 [R-L+2,L-1] 改一个，贡献是 R-L+1
		// 如果在 R-L+2 改了一个，答案会增加当且仅当 R-L+2 < L
		// 如果把 a_{R-L+2} 变成 a_{R+1} 答案增大 rri-ri 
		// 在 [L,R] 改一个，贡献是 i-L+1
		// 在 [R+1,n] 改一个贡献是 R-L+1 
		// 如果在 R+1 改了一个
		// 如果把 a_{R+1} 变成 a_{R-L+2} 答案增大 rri-ri
		int L = i,R = r[i];
		add(1,min(L-1,R-L+1),1,-1,i);
		add(R-L+2,L-1,0,R-L+1,i);
		if(R-L+2<=L-1)s[R-L+2].push_back({a[R+1],query(R-L+2,a[R+1],i)-r[i]});
		add(L,R,1,-L,i);
		add(R+1,n,0,R-L+1,i);
		s[R+1].push_back({a[R-L+2],query(R+1,a[R-L+2],i)-r[i]});
	}
	for(int i = 1;i<=n;i++){
		int mx =0;
		sort(s[i].begin(),s[i].end());
		int lst = 0;
		ans[i] = 0;
		for(auto x:s[i]){
			if(lst!=x.first){
				mx = x.second,lst = x.first;
			}else mx += x.second;
			ans[i] = max(ans[i],mx);
		}
		k[i]+=k[i-1],c[i]+=c[i-1];
		for(auto x:s[i]){
	//		cout << x.first << " " << x.second << endl;
		}
	//	cout << " " << ans[i] << " " << k[i] << " " << c[i] << endl;
		ans[i] += k[i]*i+c[i];
	}
	int res = 0;
	for(int i = 1;i<=n;i++)res+=ans[i]^i;
//	for(int i = 1;i<=n;i++)cout << " " << ans[i];cout << endl;
	cout << res << endl; 
}
signed main(){
	srand(time(0));
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	pw[0] = {1,1};for(int i = 1;i<=200000;i++)pw[i]=pw[i-1]*base;
	int t;cin >> t;
	while(t--)solve();
	return 0;
}/*

1
20
2 1 1 2 2 1 2 2 1 1 2 1 2 2 2 2 2 1 2 2

2
4
2 1 1 2
1
12
1 1 4 5 1 4 1 9 1 9 8 10
*/