#include <bits/stdc++.h>
#define N 200005
#define mod 1000000007998244353
#define Base 100003
// #define __int128 ll
using namespace std;
typedef long long ll;

int T;
int s[N+1];
int n, len[N];
ll tgsum[N], tgcnt[N], rec[N];
vector <int> vec0[N], vec1[N];

ll bit[N], pwBS[N];

inline void addmod (ll &a, ll b) { (a+=b)%=mod; }

void upd (int x, ll num) { while (x<=n) { addmod(bit[x], num); x+=(x&(-x)); } }
ll qry (int x) { ll res=0; while (x) { addmod(res, bit[x]); x-=(x&(-x)); } return res; }

int lcp (int i, int j)
{
    if (i>j) { swap(i, j); }
    int l=0, r=n-j+1, res=0;
    ll qi=qry(i-1), qj=qry(j-1);
    while (l<=r) {
        int md=(l+r)/2;
        ll res1=(__int128)(qry(i+md-1)-qi)*pwBS[j-i]%mod;
        ll res2=(qry(j+md-1)-qj);

        res1=(res1+mod)%mod;
        res2=(res2+mod)%mod;
        if (res1==res2) { res=md; l=md+1; }
        else { r=md-1; }
    }
    return res;
}

void add (int l, int r, ll num)
{
    tgsum[l]+=num; tgsum[r+1]-=num;
    tgcnt[l]++; tgcnt[r+1]--;
}

void clr ()
{
    for (int i=1; i<=n*2+3; i++) { tgsum[i]=0; tgcnt[i]=0; }
    for (int i=1; i<=n*2+3; i++) { bit[i]=0; }
    for (int i=1; i<=n*2+3; i++) { len[i]=0; }
    for (int i=1; i<=n*2+3; i++) { vec0[i].clear(); vec1[i].clear(); rec[i]=0; s[i]=0; }
}

void solve ()
{
    scanf("%d", &n);
    for (int i=1; i<=n; i++) { scanf("%d", &s[i]); }

    s[n+1]=0;
    // for (int i=1; i<=n; i++) { s[i]=rand()%2+1; }

    for (int i=1; i<=n; i++) { upd(i, (__int128)s[i]*pwBS[i-1]%mod); }
    for (int i=1; i<=n; i++) { len[i]=lcp(1, i); }

    ll res=0;
    for (int i=1; i<=n; i++) { res+=len[i]; }

    for (int i=2; i<=n; i++) {
        int lpre=1, rpre=len[i];
        int lsuf=i, rsuf=i+len[i]-1;
        rpre=min(rpre, lsuf-1);
        add(lpre, rpre, len[i]);
        add(lsuf, rsuf, i+len[i]-1);
        vec0[i+len[i]].push_back(i);
        if (len[i]+1>rsuf || len[i]+1<lsuf) { vec1[len[i]+1].push_back(i); }
    }

    ll prt=0, psum=0, pcnt=0;

    for (int i=1; i<=n; i++) {
        psum+=tgsum[i]; pcnt+=tgcnt[i];

        ll mxRec=0;

        int org=s[i];

        for (int j=0; j<(int)vec0[i].size(); j++) {
            int id=vec0[i][j];

            if (s[len[id]+1]==org) { continue; }

            upd(i, (__int128)(s[len[id]+1]-s[i])*pwBS[i-1] %mod );
            rec[s[len[id]+1]]+=lcp(1, id)-len[id];
            // cout<<i<<" "<<id<<" "<<len[id]<<" "<<lcp(1, id)<<endl;
            mxRec=max(mxRec, rec[s[len[id]+1]]);
            
            s[i]=s[len[id]+1];
        }
        for (int j=0; j<(int)vec1[i].size(); j++) {
            int id=vec1[i][j];

            if (s[id+len[id]]==org) { continue; }

            upd(i, (__int128)(s[id+len[id]]-s[i])*pwBS[i-1] %mod );
            rec[s[id+len[id]]]+=lcp(1, id)-len[id];
            // cout<<i<<" "<<id<<" "<<len[id]<<" "<<lcp(1, id)<<endl;
            mxRec=max(mxRec, rec[s[id+len[id]]]);

            s[i]=s[id+len[id]];
        }

        ll ans=res+mxRec-(psum-pcnt*(i-1));
        // ll tmp=0;
        // upd(i, (__int128)((org==1 ? 2 : 1)-s[i])*pwBS[i-1] %mod );
        // s[i]=(org==1 ? 2 : 1);
        // for (int j=1; j<=n; j++) { cout<<s[j]<<" "; } cout<<endl;
        // for (int j=1; j<=n; j++) {
        //     tmp+=lcp(1, j);
        // }
        // cout<<ans<<" "<<tmp<<endl;
        prt+=(ans^i);

        // cout<<res<<" "<<mxRec<<" "<<psum-pcnt*(i-1)<<endl;

        upd(i, (__int128)(org-s[i])*pwBS[i-1] %mod );
        s[i]=org;

        for (int j=0; j<(int)vec0[i].size(); j++) {
            int id=vec0[i][j];
            if (s[len[id]+1]==org) { continue; }
            rec[s[len[id]+1]]=0;
        }
        for (int j=0; j<(int)vec1[i].size(); j++) {
            int id=vec1[i][j];
            if (s[id+len[id]]==org) { continue; }
            rec[s[id+len[id]]]=0;
        }
    }

    printf("%lld\n", prt);

    clr();
}

int main ()
{
    // freopen("0test.in", "r", stdin);
    // freopen("0test.out", "w", stdout);

    pwBS[0]=1; for (int i=1; i<=200000; i++) { pwBS[i]=(__int128)pwBS[i-1]*Base%mod; }

    scanf("%d", &T);
    while (T--) { solve(); }

    return 0;
}