#include <bits/stdc++.h>

#define x first
#define y second
#define mp make_pair

using namespace std;
const int N = 2e5 + 10, INF = 1e8;
typedef long long ll;
typedef pair<int,ll> PIL;

ll s1[N], s2[N], ans;
int s[N], slen[N], s3[N], s4[N], c[N], x[N], y[N], sa[N], rk[N], height[N], f[N][19], len[N], n;
map <int, ll> mp1[N];

void get_sa()
{
    int m = n;
    for(int i = 1; i <= m; i++) c[i] = 0;
    for(int i = 1; i <= n; i++) c[x[i] = s[i]]++;
    for(int i = 1; i <= m; i++) c[i] += c[i - 1];;
    for(int i = n; i; i--) sa[c[x[i]]--] = i;

    for(int k = 1; k <= n; k <<= 1)
    {
        int num = 0;
        for(int i = n - k + 1; i <= n; 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++) c[i] = 0;
        for(int i = 1; i <= n; i++) c[x[i]]++;
        for(int i = 1; i <= m; i++) c[i] += c[i - 1];
        for(int i = n; i; i--) sa[c[x[y[i]]]--] = y[i], y[i] = 0;

        for(int i = 1; i <= n; i++) swap(x[i], y[i]); m = 0;
        for(int i = 1; i <= n; i++)
        {
            x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? m : ++m;
        }
        if(m == n) break;
    }
}

void get_height()
{
    for(int i = 1; i <= n; i++) rk[sa[i]] = i;
    for(int i = 1, k = 0; i <= n; i++)
    {
        if(rk[i] == 1) continue;
        if(k) k--;
        int j = sa[rk[i] - 1];
        while(i + k <= n && j + k <= n && s[i + k] == s[j + k]) k++;
        height[rk[i]] = k;
    }
}

void init()
{
    for(int i = 2; i <= n; i++) len[i] = len[i >> 1] + 1;
    for(int i = 1; i <= n; i++) f[i][0] = height[i];
    for(int j = 1; j <= len[n]; j++)
    {
        for(int i = 1; i + (1 << j) - 1 <= n; i++)
        {
            f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
        }
    }
}

int querymn(int l, int r)
{
    if(l > r) return INF;
    int t = len[r - l + 1];
    return min(f[l][t], f[r - (1 << t) + 1][t]);
}

int lcp(int i, int j)
{
    if(i == j) return n - i + 1;
    if(i > n || j > n) return 0;
    if(rk[i] > rk[j]) swap(i, j);
    return querymn(rk[i] + 1, rk[j]);
}

int getlcp(int i, int j, int x, int y)
{
    if(i > n || j > n) return 0;
    if(i == j) return n - i + 1;
    int len = lcp(i, j);
    if(i + len - 1 >= x - 1)
    {
        len = x - i;
        if(y == s[j + len])
        {
            len++;
            len += lcp(i + len, j + len);
        }
    }
    return len;
}

void add(int x, int y)
{
    x++;
    for(; x <= n + 1; x += x & -x) c[x] += y;
}

int ask(int x)
{
    x++;
    int res = 0;
    for(; x; x -= x & -x) res += c[x];
    return res;
}

int main()
{
    //freopen("data.in", "r", stdin);
    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &n);
        ans = 0;
        for(int i = 1; i <= n; i++)
        {
            scanf("%d", &s[i]);
            s1[i] = s2[i] = s3[i] = s4[i] = 0;
            mp1[i].clear();
        }
        get_sa(), get_height(), init();
			for(int i = 1; i <= n + 1; i++) c[i] = 0;
        for(int j = 2; j <= n; j++)
        {
            slen[j] = lcp(1, j);
            int l1 = 1, r1 = slen[j], l2 = j, r2 = j + slen[j] - 1;
            s2[l2] += j, s2[r2 + 1] -= j; s3[l2]++, s3[r2 + 1]--;
            if(r1 >= l2)
            {
                s1[r2 + 1] += slen[j];
            }
            else
            {
                s1[r1 + 1] += slen[j], s1[l2] -= slen[j], s1[r2 + 1] += slen[j];
            }
            add(slen[j], 1);
            if(r2 < n)
			{
                mp1[r1 + 1][s[r2 + 1]] = mp1[r1 + 1][s[r2 + 1]] + 1 + lcp(r1 + 2, r2 + 2);
                mp1[r2 + 1][s[r1 + 1]] = mp1[r2 + 1][s[r1 + 1]] + 1 + getlcp(r1 + 2, r2 + 2, r2 + 1, s[r1 + 1]);
            }
        }

        ll sum1 = 0, sum3 = 0; int sum2 = 0;
        for(int i = 1; i <= n; i++)
        {
            add(slen[i], -1);
            sum1 += s2[i], sum2 += s3[i], sum3 += s1[i];
            ll ans1 = 0, ans2 = 0;
            ans1 = (ll)(ask(n) - ask(i - 1)) * (i - 1) + (ll)i * sum2 - sum1 + n + sum3;
            for(auto it = mp1[i].begin(); it != mp1[i].end(); it++)
            {
						if((*it).x==s[i]&&(*it.y)) exit(0);
                ans2 = max(ans2, (*it).y);
            }
            ans = ans + ((ans1 + ans2) ^ i);
        }
        printf("%lld\n", ans);
    }
    return 0;
}

answer.code: In function ‘int main()’:
answer.code:4:11: error: ‘struct std::_Rb_tree_iterator<std::pair<const int, long long int> >’ has no member named ‘second’
    4 | #define y second
      |           ^~~~~~
answer.code:169:72: note: in expansion of macro ‘y’
  169 |                                                 if((*it).x==s[i]&&(*it.y)) exit(0);
      |                                                                        ^
answer.code:126:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  126 |     scanf("%d", &T);
      |     ~~~~~^~~~~~~~~~
answer.code:129:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  129 |         scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
answer.code:133:18: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  133 |             scanf("%d", &s[i]);
      |             ~~~~~^~~~~~~~~~~~~