#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
const int maxn = 200000;
struct SA {
	int a[maxn + 5], b[maxn + 5];
	int* rnk;
	int cnt[maxn + 5];
	int sa[maxn + 5];
	int lg[maxn + 5];
	int mn[maxn + 5][20];
	void build(int str[], int n) {
		int *x = a, *y = b, m = n;
		for (int i = 1; i <= n; i++) cnt[x[i] = str[i]]++;
		for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
		for (int i = n; i; i--) sa[cnt[x[i]]--] = i;
		for (int p = 1; p <= n; p <<= 1) {
			int w = 0;
			for (int i = n - p + 1; i <= n; i++) y[++w] = i;
			for (int i = 1; i <= n; i++)
				if (sa[i] > p) y[++w] = sa[i] - p;
			for (int i = 1; i <= n; i++) cnt[i] = 0;
			for (int i = 1; i <= n; i++) cnt[x[y[i]]]++;
			for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
			for (int i = n; i; i--) sa[cnt[x[y[i]]]--] = y[i];
			swap(x, y);
			w = 0;
			for (int i = 1; i <= n; i++)
				x[sa[i]] = (y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + p] == y[sa[i] + p]) ? w : ++w;
			if (w == n) break;
			m = w;
		}
		rnk = x;
		for (int i = 1, k = 0; i <= n; i++) {
			if (k) k--;
			while (str[i + k] == str[sa[rnk[i] - 1] + k]) k++;
			mn[rnk[i]][0] = k;
		}
		for (int i = n; i; i--)
			for (int j = 1; i + (1 << j) - 1 <= n; j++) mn[i][j] = min(mn[i + (1 << (j - 1))][j - 1], mn[i][j - 1]);
		for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
	}
	int lcp(int l, int r) {
		if (l == r) return 1E9;
		l = rnk[l], r = rnk[r];
		if (l > r) swap(l, r);
		int t = lg[r - l];
		return min(mn[l + 1][t], mn[r - (1 << t) + 1][t]);
	}
} sa;
int a[maxn + 5];
i64 dif[maxn + 5];
int ds[maxn + 5];
inline void add(int l, int r, int a, int d) {
	dif[l] += a - d, dif[r + 1] -= a + d * (r - l);
	ds[l] += d, ds[r + 1] -= d;
}
unordered_map<int, i64> ad[maxn + 5]; 
int main() {
	int T;
	scanf("%d", &T);
	while (T--) {
		int n;
		scanf("%d", &n);
		for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
		sa.build(a, n);
		add(1, n, n, 0);
		for (int i = 2; i <= n; i++) {
			int len = sa.lcp(1, i);
			if (len) {
				add(i, len + i - 1, 0, 1);
				add(1, min(len, i - 1), 0, 1);
			}
			if (len < i - 1) add(len + 1, i - 1, len, 0);
			if (len + i <= n) {
				add(len + i, n, len, 0);
				int c = a[len + 1], ex;
				if (2 * i + len - 1 <= n) {
					int tmp = min(sa.lcp(len + i + 1, len + 2), i - 2);
					ex = tmp + 1;
					if (tmp == i - 2 && a[2 * i + len - 1] == c) ex += sa.lcp(2 * i + len, len + i + 1) + 1;
				} else ex = sa.lcp(len + i + 1, len + 2) + 1;
				ad[len + i][c] += ex;
				if (len + 1 < i) ad[len + 1][a[len + i]] += sa.lcp(len + 2, len + i + 1) + 1;
			}
		}
		i64 nw = 0, ans = 0;
		for (int i = 1; i <= n; i++) {
			ds[i] += ds[i - 1];
			nw += dif[i] + ds[i];
			i64 mx = 0;
			for (const auto &[x, y] : ad[i]) mx = max(mx, y);
			ans += (nw + mx) ^ i;
		}
		printf("%lld\n", ans);
		for (int i = 1; i <= n + 1; i++) dif[i] = ds[i] = sa.cnt[i] = sa.a[i] = sa.b[i] = 0, ad[i].clear();
	}
}