#include<iostream>
#include<cstring>
#include<vector>
#include<numeric>
#include<functional>
#include<random>
#include<map>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
const int maxn = 1e6 + 5;
static const ULL mod = (1ull << 61) - 1;
ULL power[maxn];
mt19937_64 rnd(random_device{}());
uniform_int_distribution<ULL> dist(100, mod - 1);
const ULL base = dist(rnd);

static inline ULL add(ULL a, ULL b){
    a += b;
    if (a >= mod) a -= mod;
    return a;
}

static inline ULL mul(ULL a, ULL b){
    __uint128_t c = __uint128_t(a) * b;
    return add(c >> 61, c & mod);
}

ULL merge(ULL h1, ULL h2, int len2){
    return add(mul(h1, power[len2]), h2);
}

void init(){
    power[0] = 1;
    for(int i = 1; i < maxn; i++)
        power[i] = mul(power[i - 1], base);
}

ULL query(const vector<ULL> &s, int l, int r){
    return add(s[r], mod - mul(s[l - 1], power[r - l + 1]));
}

vector<ULL> build(const string &s){
    int sz = s.size();
    vector<ULL> hashed(sz + 1);
    for (int i = 0; i < sz; i++){
        hashed[i + 1] = add(mul(hashed[i], base), s[i]);
    }
    return hashed;
}

template <typename T>
vector<ULL> build(const vector<T> &s){
    int sz = s.size();
    vector<ULL> hashed(sz + 1);
    for (int i = 0; i < sz; i++){
        hashed[i + 1] = add(mul(hashed[i], base), s[i]);
    }
    return hashed;
}

struct Info {
    ULL hsh = 0; int len = 0; 
};

Info operator+(const Info &a, const Info &b){
    return {merge(a.hsh, b.hsh, b.len), a.len + b.len};
}

template<class Info>
struct SegmentTree{
    int n;
    vector<Info> info;

    SegmentTree() {}

    SegmentTree(int n, Info _init = Info()){
        init(vector<Info>(n, _init));
    }

    SegmentTree(const vector<Info> &_init){
        init(_init);
    }

    void init(const vector<Info> &_init){
        n = (int)_init.size();
        info.assign((n << 2) + 1, Info());
        function<void(int, int, int)> build = [&](int p, int l, int r){
            if (l == r){
                info[p] = _init[l - 1];
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m + 1, r);
            pull(p);
        };
        build(1, 1, n);
    }

    void pull(int p){
        info[p] = info[2 * p] + info[2 * p + 1];
    }

    void modify(int p, int l, int r, int x, const Info &v){
        if (l == r){
            info[p] = v;
            return;
        }
        int m = (l + r) / 2;
        if (x <= m){
            modify(2 * p, l, m, x, v);
        } 
        else{
            modify(2 * p + 1, m + 1, r, x, v);
        }
        pull(p);
    }

    void modify(int p, const Info &v){
        modify(1, 1, n, p, v);
    }

    Info query(int p, int l, int r, int x, int y){
        if (l > y || r < x){
            return Info();
        }
        if (l >= x && r <= y){
            return info[p];
        }
        int m = (l + r) / 2;
        return query(2 * p, l, m, x, y) + query(2 * p + 1, m + 1, r, x, y);
    }

    Info query(int l, int r){
        return query(1, 1, n, l, r);
    }
};

vector<int> z_algorithm(const vector<int> &s){
    int n = s.size();
    vector<int> a(n);
    a[0] = n;
	for(int i = 1, l = 0, r = 0; i < n; i++){
		if (i <= r) a[i] = min(a[i - l], r - i + 1);
		while(i + a[i] < n && s[i + a[i]] == s[a[i]]) ++a[i];
		if (i + a[i] - 1 > r) l = i, r = i + a[i] - 1;
	}
    return a;
}

int lcp(SegmentTree<Info> &seg, int l1, int r1, int l2, int r2){
    int len = min(r1 - l1 + 1, r2 - l2 + 1);
    int l = 0, r = len;
    while(l < r){
        int mid = (l + r + 1) / 2;
        if (seg.query(l1, l1 + mid - 1).hsh == seg.query(l2, l2 + mid - 1).hsh) l = mid;
        else r = mid - 1;
    }
    return r;
}

template<typename T>
struct Fenwick{
    int n;
    vector<T> tr;

    Fenwick(int n) : n(n), tr(n + 1, 0){}

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

    void modify(int x, T c){
        for(int i = x; i <= n; i += lowbit(i)) tr[i] += c;
    }

    void modify(int l, int r, T c){
        modify(l, c);
        if (r + 1 <= n) modify(r + 1, -c);
    }

    T query(int x){
        T res = T();
        for(int i = x; i; i -= lowbit(i)) res += tr[i];
        return res;
    }

    T query(int l, int r){
        return query(r) - query(l - 1);
    }

    int find_first(T sum){
        int ans = 0; T val = 0;
        for(int i = __lg(n); i >= 0; i--){
            if ((ans | (1 << i)) <= n && val + tr[ans | (1 << i)] < sum){
                ans |= 1 << i;
                val += tr[ans];
            }
        }
        return ans + 1;
    }

    int find_last(T sum){
        int ans = 0; T val = 0;
        for(int i = __lg(n); i >= 0; i--){
            if ((ans | (1 << i)) <= n && val + tr[ans | (1 << i)] <= sum){
                ans |= 1 << i;
                val += tr[ans];
            }
        }
        return ans;
    }

};
using BIT = Fenwick<LL>;

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    init();
    int T;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        vector<int> a(n);
        vector<Info> init(n);
        for(int i = 0; i < n; i++) 
            cin >> a[i], init[i] = {(ULL)a[i], 1};
        auto z = z_algorithm(a);
        a.insert(a.begin(), 0);
        SegmentTree<Info> seg(init);
        LL sum = 0;
        for(int i = 0; i < z.size(); i++){
            sum += z[i];
        }
        
        vector<map<int, LL> > mp(n + 1);
        for(int i = 2; i <= n; i++){
            int len = z[i - 1];
            if (i + len <= n){
                // 修改 len + 1
                {
                    seg.modify(len + 1, {ULL(a[i + len]), 1});
                    mp[len + 1][a[i + len]] += lcp(seg, len + 1, n, i + len, n);
                    seg.modify(len + 1, {ULL(a[len + 1]), 1});
                }
                // 修改 i + len
                {
                    seg.modify(i + len, {ULL(a[len + 1]), 1});
                    mp[i + len][a[len + 1]] += lcp(seg, len + 1, n, i + len, n);
                    seg.modify(i + len, {ULL(a[i + len]), 1});
                }
            }
        }
        vector<LL> cost(n + 1);
        {
            BIT bit1(n), bit2(n);
            for(int i = 2; i <= n; i++){
                bit1.modify(i + z[i - 1] - 1, 1);
                bit2.modify(i + z[i - 1] - 1, i + z[i - 1] - 1);
                LL c1 = bit1.query(i, n);
                LL c2 = bit2.query(i, n);
                cost[i] += c2 - c1 * (i - 1);
            }
        }
        {
            BIT bit1(n), bit2(n);
            for(int i = n; i >= 1; i--){
                LL c1 = bit1.query(i, n);
                LL c2 = bit2.query(i, n);
                cost[i] += c2 - c1 * (i - 1);
                if (i != 1 && z[i - 1]){
                    bit1.modify(z[i - 1], 1);
                    bit2.modify(z[i - 1], z[i - 1]);
                }
            }
        }
        LL ans = 0;
        for(int i = 1; i <= n; i++){
            LL mx = 0;
            for(auto [x, y] : mp[i]){
                mx = max(mx, y);
            }
            ans += (sum + mx - cost[i]) ^ i;
        }
        cout << ans << '\n';
    }

}