#include<bits/stdc++.h>
#define ull unsigned long long
#define ui unsigned int
#define ld long double
#define ll long long
#define lll __int128
#define fi first
#define se second
#define e emplace
#define eb emplace_back
#define db double
#define ef emplace_front
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vp vector<pii>
#define mp make_pair

//#define LOCALJUDGE
#define int ll
bool ST;
static const ll MOD=998244353,Phi=998244352,inv2=499122177,Root=3,iRoot=332748118;
static const ll inf=1073741823,INF=4557430888798830399;
static const double eps=1e-8,pi=3.1415926535;
char in[1<<20],*p1=in,*p2=in;
using namespace std;
#define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,1<<20,stdin),p1==p2)?EOF:*p1++)
struct tup{int x,y,z;tup(int X=0,int Y=0,int Z=0){x=X,y=Y,z=Z;}};
namespace FastIO
{
	template<typename T> inline void write(T x,char ch=' ')
	{
		if(is_same<char,T>::value)putchar(x);
		else
		{
			if(x<0)x=-x,putchar('-');
			static char st[25];int top=0;
			do{st[top++]=x%10+'0',x/=10;}while(x);
			while(top)putchar(st[--top]);
		}
		ch!='~'?putchar(ch):0;
	}
	inline void write(const char*x,char ch=' ')
	{
		for(int i=0;x[i]!='\0';++i)putchar(x[i]);
		ch!='~'?putchar(ch):0;
	}
	inline void read(char&s){do s=getchar();while(s=='\n'||s==' ');}
	inline void read(char s[])
	{
		int len=0;char st;
		do st=getchar();while(st=='\n'||st==' ');
		s[++len]=st,st=getchar();
		while(st!='\n'&&st!=' ')s[++len]=st,st=getchar();
		s[++len]='\0';
	}
	template<typename T> inline void read(T &s)
	{
		s=0;char ch=getchar();
		while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
		bool tf=(ch=='-')&&(ch=getchar());
		while((ch>='0')&&(ch<='9'))s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
		s=(tf?-s:s);
	}
	template<typename T1,typename T2> inline void read(pair<T1,T2> &s){read(s.fi),read(s.se);}
	template<typename T,typename...Args> inline void write(T x,Args...args){write(x,'~'),write(args...);}
	template<typename T,typename...Args> inline void read(T&x,Args&...args){read(x),read(args...);}
}
using namespace FastIO;
namespace MTool
{
	inline int Cadd(int a,int b){return (ll)a+b>=MOD?(ll)a+b-MOD:a+b;}
	inline int Cdel(int a,int b){return a-b<0?a-b+MOD:a-b;}
	inline int Cmul(int a,int b){return 1ll*a*b%MOD;}
	inline int sqr(int a){return 1ll*a*a%MOD;}
	inline void Madd(int&a,int b){a=((ll)a+b>=MOD?(ll)a+b-MOD:a+b);}
	inline void Mdel(int&a,int b){a=(a-b<0?a-b+MOD:a-b);}
	inline void Mmul(int&a,int b){a=1ll*a*b%MOD;}
	template<typename T> inline bool Mmax(T&a,T b){return a<b?a=b,1:0;}
	template<typename T> inline bool Mmin(T&a,T b){return a>b?a=b,1:0;}
	template<typename...Args> inline void Madd(int&a,int b,Args...args){Madd(a,b),Madd(a,args...);}
	template<typename...Args> inline void Mmul(int&a,int b,Args...args){Mmul(a,b),Mmul(a,args...);}
	template<typename...Args> inline void Mdel(int&a,int b,Args...args){Mdel(a,b),Mdel(a,args...);}
	template<typename...Args> inline int Cadd(int a,int b,Args...args){return Cadd(Cadd(a,b),args...);}
	template<typename...Args> inline int Cmul(int a,int b,Args...args){return Cmul(Cmul(a,b),args...);}
	template<typename...Args> inline int Cdel(int a,int b,Args...args){return Cdel(Cdel(a,b),args...);}
	template<typename...Args,typename T> inline bool Mmax(T&a,T b,Args...args){return Mmax(a,b)|Mmax(a,args...);}
	template<typename...Args,typename T> inline bool Mmin(T&a,T b,Args...args){return Mmin(a,b)|Mmin(a,args...);}
	inline int power(int x,int y){int s=1;for(;y;y>>=1,Mmul(x,x))if(y&1)Mmul(s,x);return s;}
}
using namespace MTool;
namespace WrongAnswer_90
{
	int T,m,n,ans[200010],c1[200010],c2[200010],b[400010],s[200010],x[400010],y[400010],F[18][200010],rk[200010],sa[200010];
	vector<pii> ve[200010];
	inline int LCP(int x,int y)
	{
		if(x>n||y>n)return 0;
		if(x==y)return n-x+1;
		if((x=rk[x])>(y=rk[y]))swap(x,y);
		int k=__lg(y-x++);
		return min(F[k][x],F[k][y-(1<<k)+1]);
	}
	void modify(int x,int y,int st){if(x>y)return;c2[x+1]++,c2[y+1]--,c1[x]+=st,c1[y+1]-=st+y-x;}
	bool cmp(pii a,pii b){return a.fi<b.fi;}
	inline void mian()
	{
		read(T);
		for(int _=1;_<=T;++_)
		{
			read(n),m=n,s[n+1]=0;
			for(int i=1;i<=n;++i)read(s[i]);
			for(int i=1;i<=m;++i)b[i]=0;
			for(int i=1;i<=n;++i)++b[x[i]=s[i]];
			for(int i=2;i<=m;++i)b[i]+=b[i-1];
			for(int i=1;i<=n;++i)sa[b[s[i]]--]=i;
			for(int k=1,num=0;k<=n;k<<=1,num=0)
			{
				for(int i=n;i>n-k;--i)y[++num]=i;
				for(int i=1;i<=n;++i)if(sa[i]>k)y[++num]=sa[i]-k;
				for(int i=1;i<=m;++i)b[i]=0;
				for(int i=1;i<=n;++i)++b[x[i]];
				for(int i=2;i<=m;++i)b[i]+=b[i-1];
				for(int i=n;i>=1;--i)sa[b[x[y[i]]]--]=y[i];
				for(int i=1;i<=n;++i)swap(x[i],y[i]);
				x[sa[1]]=1;
				for(int i=2;i<=n;++i)
				{
					if(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])x[sa[i]]=x[sa[i-1]];
					else x[sa[i]]=x[sa[i-1]]+1;
				}
				if((m=x[sa[n]])==n)break;
			}
			for(int i=1;i<=n;++i)rk[sa[i]]=i;
			for(int i=1,k=0;i<=n;++i,k?--k:0)
			{
				while(s[i+k]==s[sa[rk[i]-1]+k])++k;
				F[0][rk[i]]=k;
			}
			for(int i=1;(1<<i)<=n;++i)
			{
				for(int j=1;j+(1<<i)-1<=n;++j)
				F[i][j]=min(F[i-1][j],F[i-1][j+(1<<(i-1))]);
			}
			for(int i=0;i<=n;++i)ve[i].clear(),ans[i]=c1[i]=c2[i]=0;
			c1[0]=n;
			for(int i=2;i<=n;++i)
			{
				int x=LCP(1,i);
				if(x+1<i)
				{
					modify(1,x,0);
					if(i+x<=n)ve[x+1].eb(mp(s[i+x],1+LCP(x+2,i+x+1)));
					c1[x+1]+=x,c1[i]-=x;
					modify(i,i+x-1,0);
					int nw=x+1+LCP(x+2,i+x+1);
					if(s[x+1]!=s[i+i+x-1])Mmin(nw,i+x-1);
					else if(nw==i+x-1)nw+=1+LCP(i+x+1,i+i+x);
					ve[i+x].eb(mp(s[x+1],nw));
					c1[i+x+1]+=x;
				}
				else
				{
					modify(1,i-1,0);
					modify(i,i+x-1,0);
					int nw=x+1+LCP(x+2,i+x+1);
					if(s[x+1]!=s[i+i+x-1])Mmin(nw,i+x-1);
					else if(nw==i+x-1)nw+=1+LCP(i+x+1,i+i+x);
					ve[i+x].eb(mp(s[x+1],max(0ll,nw-x)));
					c1[i+x]+=x;
				}
			}
			for(int i=1;i<=n;++i)c2[i]+=c2[i-1];
			ll fin=0;
			for(int i=1;i<=n;++i)
			{
				c1[i]+=c1[i-1]+c2[i],ans[i]=c1[i];
				sort(ve[i].begin(),ve[i].end());
				for(int j=0,sum=0;j<(int)ve[i].size();++j)
				{
					sum+=ve[i][j].se;
					if(j==(int)ve[i].size()-1||ve[i][j].fi!=ve[i][j+1].fi)
					Mmax(ans[i],c1[i]+sum),sum=0;
				}
				fin+=ans[i]^i;
			}
			write(fin,'\n');
		}
	}
}
bool ED;
signed main()
{
	#ifdef LOCALJUDGE
	freopen("1.in","r",stdin);
	freopen("1.out","w",stdout);
	#endif
	double st=clock();
	WrongAnswer_90::mian();
	double ed=clock();
	#ifndef LOCALJUDGE
 	cerr<<endl;
	#endif
 	cerr<<"Time: "<<ed-st<<" ms\n";
	#ifdef LOCALJUDGE
 	cerr<<"     ";
	#endif
 	cerr<<"Memory: "<<abs(&ST-&ED)/1024.0/1024.0<<" MB\n";
	return 0;
}