//vanitas vanitatum et omnia vanitas
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
template<typename T,typename U>
T ceil(T x, U y) {return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U>
T floor(T x, U y) {return (x>0?x/y:(x-y+1)/y);}
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x)  {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x)  {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x)  {return (x==0?-1:__builtin_ctzll(x));}

#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef tuple<int,int,int> tiii;
int read() {
  int x=0,w=1; char c=getchar(); 
  while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
  while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();} 
  return x*w;
}

const int N=2e5+5,base=19260817,mod=1e9+7;
int n,a[N],b[N],h[N],d[N],ans;
map<int,int> f[N];

int hsh(int l,int r) {
  return (h[r]-h[l-1]*b[r-l+1]%mod+mod)%mod;
}
int lcp(int x,int y) {
  int k=0,l=1,r=n-y+1;
  while(l<=r) {
    int mid=l+r>>1;
    if(hsh(x,x+mid-1)==hsh(y,y+mid-1)) k=mid, l=mid+1;
    else r=mid-1;
  }
  return k;
}

void solve() {
  n=read(); rep(i,1,n) a[i]=read();
  b[0]=1; rep(i,1,n) b[i]=b[i-1]*base%mod;
  rep(i,1,n) h[i]=(h[i-1]*base+a[i])%mod;
  rep(i,0,n+1) d[i]=0, f[i].clear(); ans=0;
  rep(i,1,n) {
    //cout<<"WwwwwwwwwwwwwwwwwwwwwwwwwwwwwK "<<i<<endl;
    int k=lcp(1,i);
    int j=i+k-1; ans+=k;
    if(i!=1&&i<=j) {
      d[i]+=j-i+1, d[i+1]+=i-j-2, d[j+2]+=1;
      //cout<<"RED "<<i<<" "<<j<<" "<<j-i+1<<endl;;
    }
    if(j<n) {
      int p=lcp(k+2,j+2)+1; chmin(p,j-k);
      //cout<<"   "<<i<<" "<<j<<" "<<k<<" "<<p<<" "<<a[j+1]<<" "<<a[i+p]<<endl;
      if(p<j-k||a[k+1]!=a[i+k+p]) {
        //cout<<"         a  "<<j+1<<" "<<p<<" "<<a[k+1]<<" "<<a[i+p]<<endl;
        f[j+1][a[k+1]]+=p;
      } else {
        int q=lcp(j+2,i+k+p+1)+1;
        //cout<<"         b  "<<j+1<<" "<<p<<" "<<q<<endl;
        f[j+1][a[k+1]]+=p+q;
      }
    }
    int t=min(i-1,k);
    //cout<<i<<" "<<t<<" "<<k<<endl;
    if(t) {
      d[1]+=k, d[2]-=k+1, d[t+1]-=k-t, d[t+2]+=k-t+1;
      //cout<<"DER "<<1<<" "<<t<<" "<<k<<endl;
    }
    if(i>k+1&&j<n) {
      int p=lcp(k+2,j+2)+1;
      //cout<<"     "<<i<<" "<<j+1<<' '<<k+1<<" "<<a[j+1]<<" "<<p<<endl;
      f[k+1][a[j+1]]+=p;
    }
  }
  rep(i,1,n) d[i]+=d[i-1];
  rep(i,1,n) d[i]+=d[i-1]; int pans=0;
  rep(i,1,n) {
    int res=ans-d[i], ex=0;
    //cout<<d[i]<<endl;
    for(auto [x,y]:f[i]) chmax(ex,y);
    res+=ex; pans+=(res^i);
    //cout<<i<<" "<<res<<endl;
  }
  if(pans==65) {
    cout<<"N: "<<n<<endl;
    rep(i,1,n) cout<<a[i]<<" "; puts("");
  }
  printf("%lld\n",pans);
}

signed main() {
  int T=read(); while(T--) solve();
  return 0;
}