#include <bits/stdc++.h>

using i64 = long long;

template<int m1, int m2>
struct Hash {
    int x, y;
    Hash(i64 a, i64 b): x(a % m1), y(b % m2) {
        if (x < 0) x += m1;
        if (y < 0) y += m2;
    }
    Hash(i64 a = 0): Hash(a, a) {}

    using H = Hash;
    static int norm(int x, int mod) { return x >= mod ? x - mod : x < 0 ? x + mod : x; }
    friend H operator +(H a, H b) { a.x = norm(a.x + b.x, m1); a.y = norm(a.y + b.y, m2); return a; }
    friend H operator -(H a, H b) { a.x = norm(a.x - b.x, m1); a.y = norm(a.y - b.y, m2); return a; }
    friend H operator *(H a, H b) { return H{1ll * a.x * b.x, 1ll * a.y * b.y}; }
    
    friend bool operator ==(H a, H b) { return std::tie(a.x, a.y) == std::tie(b.x, b.y); }
    friend bool operator !=(H a, H b) { return std::tie(a.x, a.y) != std::tie(b.x, b.y); }
    friend bool operator <(H a, H b) { return std::tie(a.x, a.y) < std::tie(b.x, b.y); }
};
using hashv = Hash<1000000007, 1000050131>;

struct Fenwick_Tree{
    std::vector<hashv> c;
    int n;
    Fenwick_Tree(int n) : n(n) {
        c.resize(n + 1);
    }
    void add(int x, hashv y) {
        for (int i = x; i <= n; i += i & -i) {
            c[i] = c[i] + y;
        }
    }
    hashv query(int x) {
        hashv res = (0, 0);
        for (int i = x; i > 0; i -= i & -i) {
            res = res + c[i];
        }
        return res;
    }
};

void solve(){
    int n;
    std::cin >> n;
    std::vector<hashv> bin(n + 1);
    std::vector<int> a(n + 1);
    bin[0] = hashv(1, 1);
    Fenwick_Tree tree(n);
    for (int i = 1; i <= n; i += 1){
        bin[i] = bin[i - 1] * hashv(233, 13331);
        int x;
        std::cin >> x;
        tree.add(i, hashv(x, x) * bin[i]);
        a[i] = x;
    }

    auto modify = [&](int i, int v){
        tree.add(i, hashv(-a[i], -a[i]) * bin[i]);
        a[i] = v;
        tree.add(i, hashv(a[i], a[i]) * bin[i]);
    };

    auto lcp = [&](int i, int j) {
        int hi = n - std::max(i, j) + 1;
        int lo = 1, ans = 0;
        while(hi >= lo) {
            int mid = lo + hi >> 1;
            if ((tree.query(i + mid - 1) - tree.query(i - 1)) * bin[j] == (tree.query(j + mid - 1) - tree.query(j - 1)) * bin[i]) {
                lo = mid + 1;
                ans = mid;
            }
            else {
                hi = mid - 1;
            }
        }
        return ans;
    };

    
    std::vector e1(n + 2, std::vector<std::tuple<int, int, int> >()) ;
    std::vector e2(n + 2, std::vector<std::pair<int, int> >()) ;
    i64 sum = 0;
    for (int i = 1; i <= n; i += 1){
        sum += lcp(1, i);
    }

    auto add_e1 = [&](int l, int r, int c) {
        if (l > r) return;
        // if (l <= 4 && 4 <= r) std::cerr << "e1: " << l << " " << r << " " << c << "\n";
        e1[l].emplace_back(1, l, c);
        e1[r + 1].emplace_back(-1, l, c);
    };

    auto add_e2 = [&](int x, int v, int c) {
        // if (x == 4) std::cerr << "e2: " << x << " " << v << " " << c << "\n";
        e2[x].emplace_back(v, c);
    };

    for (int i = 2; i <= n; i += 1) {
        int x = lcp(1, i);
        if (x < i) {
            add_e1(1, x, x);
            add_e1(i, i + x - 1, x);
            if (i + x <= n) {
                int t = a[i + x];
                modify(i + x, a[x + 1]);
                int y = lcp(1, i) - x;
                modify(i + x, t);
                
                // std::cerr << "!\n";
                add_e2(i + x, a[x + 1], y);
                if (x + 1 != i) {
                    t = a[x + 1];
                    modify(x + 1, a[i + x]);
                    y = lcp(1, i) - x;
                    modify(x + 1, t);

                    // std::cerr << "?\n";
                    add_e2(x + 1, a[x + i], y);
                }
            }
        }
        else {
            add_e1(1, i - 1, x);
            add_e1(i, i + x - 1, x);
            if (i + x <= n) {
                int t = a[i + x];
                modify(i + x, a[x + 1]);
                int y = lcp(1, i) - x;
                add_e2(i + x, a[x + 1], y);
                modify(i + x, t);
            }
        }
    }

    i64 cnt = 0;
    i64 delta = 0;
    i64 ans = 0;
    for (int i = 1; i <= n; i += 1) {
        for (auto [t, l, c] : e1[i]) {
            cnt += t;
            delta -= t * (l + c);
        }
        i64 res = sum + delta + 1ll * i * cnt;
        std::sort(e2[i].begin(), e2[i].end());
        for (int j = 0; j < e2[i].size(); j += 1) {
            int k = j;
            i64 bonus = 0;
            while(k < e2[i].size() && e2[i][j].first == e2[i][k].first) {
                bonus += e2[i][k].second;
                k += 1;
            }
            // std::cerr << i << " " << sum << " " << delta << " " << bonus << " " << cnt << "\n";
            res = std::max(res, sum + delta + bonus + 1ll * i * cnt);
            j = k - 1;
        }
        // std::cout << res << " \n"[i == n];
        ans += res ^ i;
    }
    std::cout << ans << "\n";
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int T;
    std::cin >> T;
    while(T--) solve();
    return 0;
}