#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int,int>
#define piii tuple<int,int,int>
#define mp make_pair
#define mt make_tuple
#define x first
#define y second
#define fi first
#define se second
#define ers erase
#define ins insert
#define it iterator
#define lb lower_bound
#define ub upper_bound
#define exc(exp) if(exp)continue;
#define ret(exp) if(exp)return;
#define stop(exp) if(exp)break;
#define let(var...) int var;tie(var)
#define siz(vec) ((int)((vec).size()))
#define all(vec) (vec).begin(),(vec).end()
#define unq(vec) sort(all(vec)),(vec).erase(unique(all(vec)),(vec).end())
#define deb(var) cerr<<#var<<'='<<(var)<<"; "
#define debl(var) cerr<<#var<<'='<<(var)<<";\n"
#define ll long long
#define inf (long long)(1e18)
void chkmax(int &x,int y){if(x<y)x=y;}
void chkmin(int &x,int y){if(x>y)x=y;}
const int mod=998244353,base=1437;
int bpow[200010];
void Add(int &x,int y){x=x+y<mod?x+y:x+y-mod;}
int add(int x,int y){return x+y<mod?x+y:x+y-mod;}
int power(int x,int y){
	int ans=1;for(;y;y>>=1,(x*=x)%=mod)if(y&1)(ans*=x)%=mod;return ans;
}

int n,s[200010],h[200010];
int hsh(int i,int j){
	return (h[j]-h[i-1]*bpow[j-i+1]%mod+mod)%mod;
}
int lcp(int i,int j){
	if(i>j)swap(i,j);
	if(i==j)return n-i+1;
	int l=0,r=n-j+1,mid;
	while(l<r){
		mid=(l+r+1)>>1;
		if(hsh(i,i+mid-1)==hsh(j,j+mid-1))l=mid;else r=mid-1;
	}				return l;
}
int k[200010],b[200010]; map<int,int> p[200010];
void work(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>s[i];
	s[n+1]=n+1;
	for(int i=1;i<=n+1;i++)
		h[i]=(h[i-1]*base+s[i])%mod,k[i]=b[i]=0,p[i].clear(); 
	for(int i=2;i<=n;i++){
		int L=lcp(1,i);
		if(n-i+1<i){
			k[1]++,k[L+1]--,b[1]--,b[L+1]++;           // change [1,L]
			if(i+L<=n)p[L+1][s[i+L]]+=(lcp(i+L+1,L+2)+L+1)-L;    // change L+1 to match
			b[L+1]+=L,b[i]-=L;                         // change [L+1,i-1]
			
			k[i]++,k[i+L]--,b[i]-=i,b[i+L]+=i;         // change [i,i+L-1]
			if(i+L<=n)p[i+L][s[L+1]]+=(lcp(i+L+1,L+2)+L+1)-L;    // change i+L to match
			b[i+L]+=L;        	  					   // change [i+L,n]
		}else{
			k[i]++,k[i+L]--,b[i]-=i,b[i+L]+=i;         // change [i,i+L-1]
			if(i+L<=n){
				int lc=min(lcp(i+L+1,L+2),(i+L)-(L+2));
				deb(lc);
				if(L+2+lc==i+L&&s[L+1]==s[i+L+i-1])lc+=1+lcp(i+L+1,i+L+i); 
				p[i+L][s[L+1]]+=lc+1;
			}
			b[i+L]+=L;        	  					   // change [i+L,n]
			
			if(L+1<i){
				k[1]++,k[L+1]--,b[1]--,b[L+1]++;           // change [1,i-1]
				b[L+1]+=L,b[i]-=L;
				if(i+L<=n)p[L+1][s[i+L]]+=(lcp(i+L+1,L+2)+L+1)-L;    // change L+1 to match
			}else{
				k[1]++,k[i]--,b[1]--,b[i]++;
			}
		}
	} 
	int out=0;
	for(int i=1;i<=n;i++){
		k[i]+=k[i-1],b[i]+=b[i-1];
		int ans=k[i]*i+b[i];
		for(auto t:p[i])
			chkmax(ans,k[i]*i+b[i]+t.se);
		deb(i),debl(ans+n);		out+=(ans+n)^i;
	}					cout<<out<<'\n';
}
signed main(){
	bpow[0]=1;
	for(int i=1;i<=2e5;i++)
		bpow[i]=bpow[i-1]*base%mod;
	ios::sync_with_stdio(0),
	cin.tie(0),cout.tie(0);
	int T=1;cin>>T;while(T--)work();
}
/*
 * CONTINUE, NON-STOPPING, FOR THE FAITH
 * START TYPING IF YOU DON'T KNOW WHAT TO DO
 * STOP TYPING IF YOU DON'T KNOW WHAT YOU'RE DOING
 */