#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cassert>
#include<cstdio>
#include<cctype>
#include<vector>
#include<bitset>
#include<random>
#include<ctime>
#include<queue>
#include<cmath>
#include<list>
#include<map>
#include<set>
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define pll pair<long long,long long>
#define FF fflush(stdout)
#define inf 0x3f3f3f3f
#define endl "\n"
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
//char buf[1<<20],*p1,*p2;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
inline int read()
{
    int s=0,f=1;
    char x=getchar();
    while(!isdigit(x))f=(x=='-'?-1:1),x=getchar();
    while(isdigit(x))s=s*10+x-'0',x=getchar();
    return s*f;
}
const int p=1e9+7,p2=998244853;
//ll ksm(int a,int b){ll ans=1,bs=a;while(b){if(b&1)ans=ans*bs%p;bs=bs*bs%p;b>>=1;}return ans;}
mt19937 rd(time(0));
#define reaD read
int s[200005];
ll hs1[200005],hs2[200005];
ll pw[200005],pw2[200005];
ll cal(int l,int r,int op)
{
    int len=r-l+1;
    if(op==0)
    return (hs1[r]-(l==0?0:hs1[l-1])*pw[len]%p+p)%p;
    else
    return (hs2[r]-(l==0?0:hs2[l-1])*pw2[len]%p2+p2)%p2;
}
int n;
int lcp(int l1,int l2)
{
	int l=1,r=n-l2;
	while(l<=r)
	{
		int mid=(l+r)>>1; 
		if(cal(l1,l1+mid-1,0)==cal(l2,l2+mid-1,0)&&cal(l1,l1+mid-1,1)==cal(l2,l2+mid-1,1))
		l=mid+1;
		else r=mid-1;
	}
	return r;
}
ll s0[200005],s1[200005];
void mdf(int id,int k)
{//cout<<"mdf: "<<id<<" "<<k<<endl;
	s0[id]-=k;
	s0[id+1]+=k+1;
	s0[id+1+k]--;
    //for(int i=0;i<=10;i++)cout<<s0[i]<<" ";puts("");
}
map<int,ll> m[200005];
int main()
{
    pw[0]=pw2[0]=1;
    for(int i=1;i<=200000;i++)
    pw[i]=pw[i-1]*131%p,pw2[i]=pw2[i-1]*131%p2;
    int T=reaD();
    while(T--)
    {
        n=reaD();
        for(int i=0;i<n;i++)
		s[i]=read(); 
        hs1[0]=hs2[0]=s[0];
        for(int i=1;i<n;i++)
        hs1[i]=(hs1[i-1]*131+s[i])%p,hs2[i]=(hs2[i-1]*131+s[i])%p2;
        ll ori=0;
		for(int i=0;i<n;i++)
		{
			int pos=lcp(0,i)+i;
			int posori=pos-i;
			ori+=posori;
			if(posori<i)
			{//cout<<"op1 "<<i<<endl;
				mdf(0,posori);
				mdf(i,posori);
				if(pos<n)
				{
					m[posori][s[pos]]+=1+lcp(posori+1,pos+1);
					int len=lcp(posori+1,pos+1);
                    if(posori+1+len>pos)
                    len=pos-posori-1;
					else if(posori+1+len==pos&&pos+1+len<n&&s[posori]==s[pos+1+len])
					len+=1+lcp(pos+1,pos+1+len+1);
					m[pos][s[posori]]+=1+len;	
				}
			}
			else
			{
				s1[0]+=i;
				s1[i]-=i;
				if(pos<n)
				{
					mdf(0,pos);
					int len=lcp(posori+1,pos+1);
                    if(posori+1+len>pos)
                    len=pos-posori-1;
					else if(posori+1+len==pos&&pos+1+len<n&&s[posori]==s[pos+1+len])
					len+=1+lcp(pos+1,pos+1+len+1);
					m[pos][s[posori]]+=1+len;
				}
			}//cout<<m[1][2]<<endl;
		}
		for(int i=0;i<n;i++)
		{
			if(i)
			s0[i]+=s0[i-1];
			s1[i]+=s0[i];
			if(i)
			s1[i]+=s1[i-1];//cout<<s1[i]<<" ";
		}//puts("");
		ll anss=0;
		for(int i=0;i<n;i++)
		{
            ll ans=ori+s1[i];
			for(auto j:m[i])
			ans=max(ans,ori+s1[i]+j.se);//,cout<<i<<" "<<j.fi<<" "<<j.se<<" "<<ans<<endl;
            // cout<<ans<<" ";
			anss+=ans^(i+1);
		}
		// puts("");
		printf("%lld\n",anss);
		
		for(int i=0;i<n+3;i++)
		s0[i]=s1[i]=0,m[i].clear();
    }
    //system("pause");
    return 0;
}