#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;

vector<int> get_z(vector<int> A) {
    vector<int> z(A.size());
    int j = 0;
    for (int i = 1; i < A.size(); ++i) {
        if (j + z[j] > i)
            z[i] = min(j + z[j] - i, z[i - j]);
        while (i + z[i] < A.size() && A[i + z[i]] == A[z[i]])
            ++z[i];
        if (i + z[i] > j + z[j])
            j = i;
    }
    return z;
}

vector<int> get_pi(vector<int> A) {
    vector<int> pi(A.size());
    for (int i = 1; i < A.size(); ++i) {
        int j = pi[i - 1];
        while (j != -1 && A[j] != A[i])
            j = (j == 0 ? -1 : pi[j - 1]);
        pi[i] = j + 1;
    }
    return pi;
}

const int MAXN = 200200;
const int K = 20;
int lg[MAXN];
int table[MAXN][K];

void solve() {
    int n;
    cin >> n;
    vector<int> A(n);
    for (int i = 0; i < n; ++i)
        cin >> A[i];

    // suff mass
    A.emplace_back(-1);
    int N = n + 1;
    vector<int> order(N);
    vector<int> classes(N);
    vector<int> new_order(N);
    vector<int> new_classes(N);
    vector<int> cnt(N);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&A](int a, int b) {
        return A[a] < A[b];
    });
    classes[order[0]] = 0;
    for (int i = 1; i < N; ++i)
        classes[order[i]] = classes[order[i - 1]] + (A[order[i]] == A[order[i - 1]] ? 0 : 1);
    auto safe_add = [](int a, int b, int c) {
        if (a + b < c)
            return a + b;
        return a + b - c;
    };
    for (int l = 1; l < N; l *= 2) {
        fill(cnt.begin(), cnt.end(), 0);
        for (int i = 0; i < N; ++i)
            ++cnt[classes[i]];
        for (int i = 1; i < N; ++i)
            cnt[i] += cnt[i - 1];
        for (int j = N - 1; j >= 0; --j) {
            int cur = order[j] - l;
            if (cur < 0)
                cur += N;
            --cnt[classes[cur]];
            new_order[cnt[classes[cur]]] = cur;
        }
        new_classes[new_order[0]] = 0;
        for (int i = 1; i < N; ++i) {
            new_classes[new_order[i]] = new_classes[new_order[i - 1]] + 
            (make_pair(classes[new_order[i]], classes[safe_add(new_order[i], l, N)]) ==
                make_pair(classes[new_order[i - 1]], classes[safe_add(new_order[i - 1], l, N)]) ? 0 : 1);
        }
        swap(classes, new_classes);
        swap(order, new_order);
    }
    vector<int> lcp(N);
    vector<int> id(N);
    for (int i = 0; i < N; ++i)
        id[order[i]] = i;
    int tmp = 0;
    for (int i = 0; i < N; ++i) {
        if (id[i] == N - 1) {
            tmp = 0;
            continue;
        }
        int j = order[id[i] + 1];
        while (i + tmp < N && j + tmp < N && A[i + tmp] == A[j + tmp])
            ++tmp;
        lcp[id[i]] = tmp;
        tmp = max(tmp - 1, 0);
    }
    for (int i = 0; i < N; ++i)
        table[i][0] = lcp[i];
    for (int j = 1; j < K; ++j) {
        for (int i = 0; i + (1 << j) <= N; ++i)
            table[i][j] = min(table[i][j - 1], table[i + (1 << (j - 1))][j - 1]);
    }
    auto get_lcp = [&](int a, int b) {
        if (a == n || b == n) return 0;
        a = id[a];
        b = id[b];
        if (a > b)
            swap(a, b);
        if (a == b)
            return N;
        int k = lg[b - a];
        return min(table[a][k], table[b - (1 << k)][k]);
    };
    

    A.pop_back();
    vector<int> pi1 = get_pi(A);
    vector<int> p(n + 1);
    p[0] = -1;
    for (int i = 0; i < n; ++i) {
        p[i + 1] = pi1[i];
    }
    vector<int> z = get_z(A);
    int64_t f0 = n;
    for (int i = 1; i < n; ++i) {
        f0 += z[i];
    }
    vector<int64_t> val(n);
    vector<int64_t> dk(n), db(n);
    for (int i = 1; i < n; ++i) {
        dk[i + z[i] - 1] += 1;
        dk[i - 1] -= 1;
        db[i - 1] -= z[i];
        if (z[i] != 0) {
            dk[z[i] - 1] += 1;
        }
        if (z[i] > i) {
            dk[z[i] - 1] -= 1;
            dk[i - 1] += 1;
            db[i - 1] += z[i] - i;
        }
    }
    int64_t cur = 0;
    int64_t k = 0;
    for (int i = n - 1; i >= 0; --i) {
        k += dk[i];
        cur += k;
        cur += db[i];
        val[i] = cur;
    }
    /**for (int i = 0; i < n; ++i) {
        cerr << val[i] << " ";
    }
    cerr << "\n";*/

    vector<int> pp(n + 1);
    for (int i = 2; i <= n; ++i) {
        if (p[i] == p[i - 1] + 1) {
            pp[i] = pp[p[i]];
        } else {
            pp[i] = i;
        }
    }
    vector<int64_t> ans(n);
    vector<map<int, int64_t>> mp(n);
    for (int i = 2; i <= n; ++i) {
        /// doing ans[i - 1]
        int v = pp[i];
        while (v != 0) {
            int v1 = p[v - 1];
            int v2 = p[v] - 1;
            while (v1 != v2) {
                int res = get_lcp(i, v1 + 1);
                mp[v1][A[i - 1]] += res + 1;
                if (res >= i - v1 - 2) {
                    res = i - v1 - 2;
                    if (i + res < n && A[i + res] == A[v1]) {
                        ++res;
                        res += get_lcp(i + res, i);
                    }
                }
                mp[i - 1][A[v1]] += res + 1;
                v1 = p[v1];
            }
            v = pp[p[v]];
        }
    }

    mp[0].clear();
    for (int i = 1; i < n; ++i) {
        mp[0][A[i]] += get_lcp(i + 1, 1) + 1;
    }
    int64_t mx = 0;
    for (auto elem : mp[0]) {
        if (elem.first != A[0]) {
            mx = max(mx, elem.second);
        }
    }
    ans[0] = mx + n;
    for (int i = 1; i < n; ++i) {
        int64_t mx = 0;
        for (auto elem : mp[i]) {
            mx = max(mx, elem.second);
        }
        ans[i] = f0 - val[i] + mx;
        /// cerr << ans[i] << " ";
    }
    /// cerr << endl;
    int64_t out = 0;
    for (int i = 0; i < n; ++i) {
        /// cerr << ans[i] << " ";
        out += (ans[i] ^ (i + 1));
    }
    cout << out << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    lg[0] = -1;
    for (int i = 1; i < MAXN; ++i)
        lg[i] = lg[i / 2] + 1;

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}