#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAX_N = 400000 + 5;

int N, str[MAX_N], sa[MAX_N], rk[MAX_N], ht[MAX_N], lcp[MAX_N], st[20][MAX_N], a[MAX_N], c[MAX_N], lg[MAX_N];
unordered_map <int, ll> bonus[MAX_N];
ll b[MAX_N], d[MAX_N];

void build_sa(int *s, int n, int *sa, int *rk, int *ht) {
	static int cnt[MAX_N], sb[MAX_N], rk_[MAX_N];
	int i, j, k = n, m, *x = rk, *y = rk_;
	for (i = 1; i <= n; i ++) cnt[s[i]] ++;
	for (i = 1; i <= k; i ++) cnt[i] += cnt[i - 1];
	for (i = n; i > 0; i --) sa[cnt[s[i]] --] = i;
	memset(cnt, 0, sizeof(int) * (k + 1));
	for (i = 1, k = 0; i <= n; i ++) rk[sa[i]] = k += s[sa[i]] != s[sa[i - 1]];
	for (m = 1; m < n && k < n; m <<= 1) {
		for (j = 1; j <= m; j ++) sb[j] = n - m + j;
		for (i = 1; i <= n; i ++) if (sa[i] > m) sb[j ++] = sa[i] - m;
		for (i = 1; i <= n; i ++) cnt[x[i]] ++;
		for (i = 1; i <= k; i ++) cnt[i] += cnt[i - 1];
		for (i = n; i > 0; i --) sa[cnt[x[sb[i]]] --] = sb[i];
		memset(cnt, 0, sizeof(int) * (k + 1));
		for (i = 1, k = 0; i <= n; i ++) y[sa[i]] = k += (x[sa[i]] != x[sa[i - 1]] || x[sa[i] + m] != x[sa[i - 1] + m]);
		swap(x, y);
	}
	if (x != rk) memcpy(rk, rk_, sizeof(int) * (n + 1));
    for (i = 1, k = 0; i <= n; i ++) {
        k -= k > 0;
        while (s[i + k] == s[sa[rk[i] - 1] + k]) k ++;
        ht[rk[i]] = k;
    }
    for (i = 1; i <= n; i ++) st[0][i] = ht[i];
    for (i = 1; i <= lg[n]; i ++) {
        for (j = 1; j + (1 << i) - 1 <= n; j ++) {
            st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << i - 1)]);
        }
    }
}

int query_lcp(int i, int j) {
    if (i == j) return N - i + 1;
    if (i > N || j > N) return 0;
    int l = rk[i], r = rk[j];
    if (r < l) swap(l, r);
    int len = lg[r - l];
    return min(st[len][l + 1], st[len][r - (1 << len) + 1]);
}

void solve() {
    scanf("%d", &N);
    for (int i = 1; i <= N; i ++) {
        scanf("%d", str + i);
        bonus[i].clear();
    }
    str[N + 1] = 0;
    build_sa(str, N, sa, rk, ht);
    for (int i = 2; i <= N; i ++) {
        lcp[i] = query_lcp(1, i);
        int p1 = lcp[i] + 1, p2 = i + lcp[i];
        assert(p2 > N || str[p1] != str[p2]);
        if (p2 <= N) {
            int exlen1 = query_lcp(p1 + 1, p2 + 1) + 1, exlen2 = exlen1;
            if (p1 + exlen1 == p2 && p2 + exlen1 <= N && str[p1] == str[p2 + exlen1]) {
                exlen1 += query_lcp(p2 + 1, p2 + exlen1 + 1) + 1;
            }else if (p1 + exlen1 > p2) {
                exlen1 = p2 - p1;
            }
            bonus[p2][str[p1]] += exlen1;
            if (p1 < i) {
                bonus[p1][str[p2]] += exlen2;
            }
        }
    }
    memset(b, 0, sizeof(ll) * (N + 1));
    memset(d, 0, sizeof(ll) * (N + 1));
    memset(a, 0, sizeof(int) * (N + 1));
    memset(c, 0, sizeof(int) * (N + 1));
    int cnt1 = 0, cnt2 = 0;
    long long sum = 0, ans = 0, pre = 0, suf = 0;
    for (int i = 2; i <= N; i ++) {
        sum += lcp[i];
        if (lcp[i] > 0) {
            cnt2 ++;
            suf += lcp[i] + 1;
            c[min(i - 1, lcp[i])] ++;
            d[min(i - 1, lcp[i])] += lcp[i] + 1;
        }
    }
    for (int i = 1; i <= N; i ++) {
        cnt1 -= a[i];
        pre -= b[i];
        if (lcp[i] > 0) {
            cnt1 ++;
            pre += lcp[i] + i;
            if (lcp[i] + i <= N) {
                a[lcp[i] + i] ++;
                b[lcp[i] + i] += lcp[i] + i;
            }
        }
        ll res = sum - pre - suf + 1ll * (cnt1 + cnt2) * i, maxbonus = 0;
        for (auto [ch, val] : bonus[i]) {
            maxbonus = max(maxbonus, val);
        }
        ans += (res + maxbonus + N) ^ i;
        cnt2 -= c[i];
        suf -= d[i];
    }
    printf("%lld\n", ans);
}

int main() {
    for (int i = 2; i < MAX_N; i ++) lg[i] = lg[i >> 1] + 1;
    
	int T;
    scanf("%d", &T);
    while (T --) solve();
	return 0;
}