#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define Mp make_pair
#define pb push_back
#define SZ(x) (int((x).size()))

typedef double db;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;

const int MAXN = 2e5 + 5;
const int Mod1 = 1e9 + 7, Mod2 = 998244353, Mod3 = 1e9 + 9;
const int Base = 1313131;
int n, a[MAXN];

struct Hash {
    int val1, val2, val3;
    Hash(int val = 0) : val1(val), val2(val), val3(val) {}
    Hash(int val1, int val2, int val3) : val1(val1), val2(val2), val3(val3) {}
} Fpow[MAXN], t[MAXN];

Hash operator+(Hash a, Hash b) {
    return Hash((a.val1 + b.val1) % Mod1, (a.val2 + b.val2) % Mod2, (a.val3 + b.val3) % Mod3);
}

Hash operator-(Hash a, Hash b) {
    return Hash((a.val1 - b.val1 + Mod1) % Mod1, (a.val2 - b.val2 + Mod2) % Mod2, (a.val3 - b.val3 + Mod3) % Mod3);
}

Hash operator*(Hash a, Hash b) {
    return Hash(1ll * a.val1 * b.val1 % Mod1, 1ll * a.val2 * b.val2 % Mod2, 1ll * a.val3 * b.val3 % Mod3);
}

bool operator==(Hash a, Hash b) {
    return a.val1 == b.val1 && a.val2 == b.val2 && a.val3 == b.val3;
}

Hash Get(int l, int r) {
    return t[r] - t[l - 1] * Fpow[r - l + 1];
}
Hash GetWithChange(int l, int r, int i, int c) {
    if (r < i || i < l) return Get(l, r);
    return t[r] - a[i] * Fpow[r - i] + c * Fpow[r - i] - t[l - 1] * Fpow[r - l + 1];
}
int pos[MAXN], len[MAXN];
int cnt[MAXN];
int cnt2[MAXN];
ll sumlen[MAXN], sumpos[MAXN];
ll sumpos2[MAXN];
ll sumlen2[MAXN];
map<int, ll> del[MAXN];

int lowbit(int x) {
    return x & -x;
}

ll val1[MAXN];
int val2[MAXN];

void add(int x, int v1, int v2) {
    for (x = n + 1 - x; x <= n; x += lowbit(x))
        val1[x] += v1, val2[x] += v2;
}
pair<ll, int> ask(int x) {
    pair<ll, int> res = make_pair(0ll, 0);
    for (x = n + 1 - x; x; x -= lowbit(x))
        res.first += val1[x], res.second += val2[x];
    return res;
}

void solve() {
    cin >> n;
    // memset(val1, 0, sizeof(val1)), memset(val2, 0, sizeof(val2));
    // memset(val1, 0, sizeof(val1)), memset(val2, 0, sizeof(val2));
    // memset(sumlen, 0, sizeof(sumlen)), memset(sumlen2, 0, sizeof(sumlen2));
    // memset(sumpos, 0, sizeof(sumpos)), memset(sumpos2, 0, sizeof(sumpos2));
    // memset(cnt, 0, sizeof(cnt)), memset(cnt2, 0, sizeof(cnt2));
    Fpow[0] = 1;
    for (int i = 1; i <= n; i++) Fpow[i] = Fpow[i - 1] * Base;
    for (int i = 1; i <= n; i++) cin >> a[i], t[i] = t[i - 1] * Base + a[i];
    for (int i = 1; i <= n; i++) {
        int l = i, r = n, ans = i - 1;
        while (l <= r) {
            int mid = l + r >> 1;
            if (Get(i, mid) == t[mid - i + 1])
                ans = mid, l = mid + 1;
            else
                r = mid - 1;
        }
        pos[i] = ans, len[i] = ans - i + 1;
        cnt[ans]++, sumpos[ans] += i, sumlen[ans] += len[i];
        cnt2[i]++, sumpos2[i] += i, sumlen2[i] += len[i];
        if (ans != n) {
            int L = ans + 2, R = n, anss = ans + 1;
            while (L <= R) {
                int mid = L + R >> 1;
                if (GetWithChange(ans + 2, mid, ans + 1, a[ans + 2 - i]) == GetWithChange(ans - i + 3, mid - i + 1, ans + 1, a[ans + 2 - i]))
                    anss = mid, L = mid + 1;
                else
                    R = mid - 1;
            }
            cout << i << ' ' << ans << ' ' << anss << '\n';
            // cerr<<i<<" "<<ans<<"\n";
            del[ans + 1][a[ans - i + 2]] += anss - ans;
        }
        if (i > len[i] + 1 && ans != n) {
            int L = ans + 2, R = n, anss = ans + 1;
            while (L <= R) {
                int mid = L + R >> 1;
                if (GetWithChange(ans + 2, mid, len[i] + 1, a[i + len[i]]) == GetWithChange(ans - i + 3, mid - i + 1, len[i] + 1, a[i + len[i]]))
                    anss = mid, L = mid + 1;
                else
                    R = mid - 1;
            }
            del[len[i] + 1][a[i + len[i]]] += anss - ans;
        }
        // l = i + 1, r = n, ans = i;
        // while(l <= r) {
        //     int mid = l + r >> 1;
        //     if(Get(i + 1, mid) == Get(2, mid - 1 + 1)) ans = mid, l = mid + 1;
        //     else r = mid - 1;
        // }
        // del[i][a[1]] += ans - i + 1;
    }
    sumlen[n + 1] = sumpos[n + 1] = cnt[n + 1] = 0;
    sumlen2[n + 1] = sumpos2[n + 1] = cnt2[n + 1] = 0;
    for (int i = n; i >= 1; i--) {
        sumlen[i] += sumlen[i + 1];
        sumpos[i] += sumpos[i + 1];
        cnt[i] += cnt[i + 1];
        sumlen2[i] += sumlen2[i + 1];
        sumpos2[i] += sumpos2[i + 1];
        cnt2[i] += cnt2[i + 1];
    }
    ll Ans = 0;
    for (int i = 1; i <= n; i++) Ans += len[i];
    ll res = 0;
    for (int i = n; i >= 1; i--) {
        ll m = Ans;
        m -= sumlen[i] - sumlen2[i + 1];
        m += 1ll * i * (cnt[i] - cnt2[i + 1]) - (sumpos[i] - sumpos2[i + 1]);
        m -= i - 1;
        m += n;
        pair<ll, int> t = ask(i);
        m -= t.first;
        m += 1ll * t.second * (i - 1);
        // cout << t.first << ' ' << t.second << ' ' << m << '\n';
        // m -= len[i];
        ll Max = 0;
        for (auto [col, val] : del[i])
            if (col != a[i]) Max = max(Max, val);
        m += Max;
        // cout<<Ans<<" "<<m<<" "<<Max<<"\n";
        res += m ^ i;
        add(len[i], len[i], 1);
    }
    cout << res << '\n';
    for (int i = 1; i <= n; i++) del[i].clear();
    for (int i = 1; i <= n; i++) val1[i] = val2[i] = 0;
    for (int i = 1; i <= n; i++) sumlen[i] = sumlen2[i] = 0, sumpos[i] = sumpos2[i] = 0, cnt[i] = cnt2[i] = 0;
}
/*
2
4
2 1 1 2
12
1 1 4 5 1 4 1 9 1 9 8 10
*/
/*
1
8 
1 1 1 2 1 2 1 1

*/
signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}