#include<bits/stdc++.h>
using namespace std;
#define ll long long
int lg[1010000];
int c[1001000],rk[1001000],t[1001000],tr[1001000],sa[1001000],n,h[1000100],f[1010000][20];
int lcp(int x,int y){
    if(x>n||y>n)return 0;
    x=rk[x],y=rk[y];if(x>y)swap(x,y);x++;
    int k=lg[y-x+1];
    return min(f[x][k],f[y-(1<<k)+1][k]);
}
void SA(){
	int m=n;
    for(int i=1;i<=n*4;i++)tr[i]=0;
	for(int i=1;i<=m;i++)t[i]=0;
	for(int i=1;i<=n;i++)t[rk[i]=c[i]]++;
	for(int i=1;i<=m;i++)t[i]+=t[i-1];
	for(int i=n;i;i--)sa[t[rk[i]]--]=i;
	for(int k=1;;k<<=1){
		int p=0;
		for(int i=n-k+1;i<=n;i++)tr[++p]=i;
		for(int i=1;i<=n;i++)if(sa[i]>k)tr[++p]=sa[i]-k;
		for(int i=1;i<=m;i++)t[i]=0;
		for(int i=1;i<=n;i++)t[rk[i]]++;
		for(int i=1;i<=m;i++)t[i]+=t[i-1];
		for(int i=n;i;i--)sa[t[rk[tr[i]]]--]=tr[i];
		rk[sa[1]]=p=1;
        for(int i=1;i<=n;i++)tr[i]=rk[i];
		for(int i=2;i<=n;i++)
		rk[sa[i]]=((tr[sa[i-1]]==tr[sa[i]]&&tr[sa[i-1]+k]==tr[sa[i]+k])?p:(++p));
		m=p;if(m==n)break;
	}
    for(int i=1,k=0;i<=n;i++){
        if(k)k--;
        int j=sa[rk[i]-1];
        while(i+k<=n&&j+k<=n&&c[i+k]==c[j+k])k++;
        f[rk[i]][0]=k;
    }
    for(int j=1;j<20;j++)for(int i=1;i+(1<<j)-1<=n;i++)
    f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
int sv(int x,int y,int cy){
    int lc=1+min(lcp(x+1,y+1),y-x-1);
    if(lc<y-x||y*2-x>n||cy!=c[y*2-x])return lc;
    return lc+1+lcp(y+1,1+y+y-x);
}
#define long long
ll c1[200100],c2[200100];
void co(int l,int r){
    c1[l]-=l,c1[r+1]+=l,c2[l]++,c2[r+1]--;
}
map<int,ll>gt[201000];
void sol(){
    scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&c[i]),c1[i]=c2[i]=0,gt[i].clear();SA();
    for(int i=2;i<=n;i++){
        int l=lcp(1,i);
        if(l+1<i){
            c1[l+1]+=l,c1[i]-=l,c1[i+l]+=l;
            co(1,l),co(i,i+l-1);
            if(i+l>n)continue;
            gt[i+l][c[l+1]]+=sv(l+1,i+l,c[l+1]),gt[l+1][c[i+l]]+=sv(l+1,i+l,c[i+l]);
        }
        else{
            co(1,i-1),co(i,i+l-1),c1[i+l]+=l;
            if(i+l>n)continue;
            gt[i+l][c[l+1]]+=sv(l+1,i+l,c[l+1]);
        }
    }
    ll ans=0;
    for(int i=1;i<=n;i++){
        c1[i]+=c1[i-1],c2[i]+=c2[i-1];
        ll ve=c1[i]+c2[i]*i+n,mx=0;
        for(auto it:gt[i])mx=max(mx,it.second);
        ve+=mx;
        ans+=(ve^i);
    }
    printf("%lld\n",ans);
}
int main(){
    lg[0]=-1;
    for(int i=1;i<=1000000;i++)lg[i]=lg[i>>1]+1;
    int T;scanf("%d",&T);while(T--)sol();
    return 0;
}