#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int nxt[maxn], ex[maxn];
// void Getnxt(int *a, int n) {
// 	int i = 0, j, po;
// 	nxt[0] = n;
// 	while(a[i] == a[i + 1] && i + 1 < n)
// 		++ i;
// 	nxt[1] = i, po = 1;
// 	for(int i = 2; i < n; ++ i) {
// 		if(nxt[i - po] + i < nxt[po] + po)
// 			nxt[i] = nxt[i - po];
// 		else {
// 			j = nxt[po] + po - i;
// 			if(j < 0)
// 				j = 0;
// 			while(i + j < n && a[j] == a[j + i])
// 				++ j;
// 			nxt[i] = j;
// 			po = i;
// 		}
// 	}
// }
// void Exkmp(int *a, int *b, int n, int m) {
// 	int i = 0, j, po;
// 	Getnxt(b, m);
// 	while(a[i] == b[i] && i < n && i < m)
// 		++ i;
// 	ex[0] = i;
// 	po = 0;
// 	for(int i = 1; i < n; ++ i) {
// 		if(nxt[i - po] + i < ex[po] + po)
// 			ex[i] = nxt[i - po];
// 		else {
// 			j = ex[po] + po - i;
// 			if(j < 0)
// 				j = 0;
// 			while(i + j < n && j < m && a[j + i] == b[j])
// 				++ j;
// 			ex[i] = j;
// 			po = i;
// 		}
// 	}
// }
int n, a[maxn << 1];
namespace SA {
	int Mem[maxn * 10], sa[maxn], h[maxn], rk[maxn];
	void Build(int m) {
		int *x = Mem, *y = Mem + (maxn << 1), *z = y + (maxn << 1);
		for(int i = 1; i <= 2 * n; ++ i) x[i] = y[i] = z[i] = 0;
		for(int i = 1; i <= m; ++ i) z[i] = 0;
		for(int i = 1; i <= n; ++ i) ++ z[x[i] = a[i]];
		for(int i = 1; i <= m; ++ i) z[i] += z[i - 1];
		for(int i = 1; i <= n; ++ i) sa[z[x[i]] --] = i;
		for(int k = 1; k <= n; k <<= 1) {
			int p = 0;
			for(int i = n - k + 1; i <= n; ++ i) y[++ p] = i;
			for(int i = 1; i <= n; ++ i) if(sa[i] > k) y[++ p] = sa[i] - k;
			for(int i = 1; i <= m; ++ i) z[i] = 0;
			for(int i = 1; i <= n; ++ i) ++ z[x[i]];
			for(int i = 1; i <= m; ++ i) z[i] += z[i - 1];
			for(int i = n; i; -- i) sa[z[x[y[i]]] --] = y[i];
			swap(x, y); p = 0;
			for(int i = 1; i <= n; ++ i) x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? p : ++ p;
			if(p == n) break;
			m = p;
		}
	}
	int st[20][maxn], bin[maxn];
	void Geth() {
		int w = 0;
		for(int i = 1; i <= n; ++ i) {
			rk[sa[i]] = i;
		}
// cerr << "? " << endl;
		for(int i = 1; i <= n; ++ i) {
			if(w) -- w;
			if(rk[i] == n)
				continue;
// cerr << "?? " << i << " " << w << endl;
			while(i + w <= n && sa[rk[i] + 1] + w <= n && a[i + w] == a[sa[rk[i] + 1] + w]) ++ w;
			h[rk[i]] = w;
		}
		bin[1] = 0;
		for(int i = 2; i <= n; ++ i)
			bin[i] = bin[i >> 1] + 1;
		for(int i = 1; i < n; ++ i) {
			st[0][i] = h[i];
		}
		// st[0][n] = 1e9;
		for(int j = 1; j < 20; ++ j) {
			for(int i = 1; i + (1 << j) - 1 < n; ++ i) {
				st[j][i] = min(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
			}
		}
	}
	int Lcp(int l, int r) {
		if(l > n || r > n)
			return 0;
		if(l == r)
			return n - l + 1;
		l = rk[l], r = rk[r];
		if(l > r)
			swap(l, r);
		-- r;
		int k = bin[r - l + 1];
		return min(st[k][l], st[k][r - (1 << k) + 1]);
	}
}
int T;
long long dif2[maxn], dif1[maxn], val[maxn];
map<int, int> chg[maxn];
void Sub(int l, int r, int s) {
// cerr << "Sub(" << l << ", " << r << ", " << s << ")" << endl;
	dif2[r] -= s;
	dif2[r - 1] -= 1 - s;
	dif2[l - 1] += s + (r - l + 1);
	if(l > 1)
		dif2[l - 2] -= s + (r - l);
}
int main() {
// 	Sub(2, 2, 1);
// 	Sub(1, 1, 1);
// 	Sub(5, 5, 1);
// 	Sub(1, 1, 1);
// 	Sub(7, 7, 1);
// 	Sub(1, 1, 1);
// 	Sub(9, 9, 1);
// 	Sub(1, 1, 1);
// for(int i = 1; i <= 12; ++ i)
// 	cerr << dif2[i] << " ";
// cerr << endl;
// 	for(int i = 12; i; -- i)
// 		dif1[i] += dif1[i + 1] + dif2[i];
// for(int i = 1; i <= 12; ++ i)
// 	cerr << dif1[i] << " ";
// cerr << endl;
// 	for(int i = 12; i; -- i)
// 		val[i] += val[i + 1] + dif1[i];
// for(int i = 1; i <= 12; ++ i)
// 	cerr << val[i] << " ";
// cerr << endl;
	for(scanf("%d", &T); T --; ) {
		scanf("%d", &n);
		// n = rand() % 100 + 1;
		for(int i = 0; i <= n + 2; ++ i) {
			val[i] = dif1[i] = dif2[i] = 0;
			chg[i].clear();
		}
		for(int i = 1; i <= n; ++ i) {
			scanf("%d", &a[i]);
			// a[i] = rand() % 2 + 1;
		}
		SA :: Build(n);
		SA :: Geth();
		// Exkmp(a, a, n, n);
		long long sum = 0;
		for(int i = 1; i <= n; ++ i) {
			ex[i] = SA :: Lcp(1, i);
			sum += ex[i];
		}
		for(int i = 2; i <= n; ++ i) {
			if(i > ex[i] + 1) { // no cross
				if(ex[i]) {
					Sub(i, i + ex[i] - 1, 1);
					Sub(1, ex[i], 1);
				}
				if(i + ex[i] <= n) {
					int lcp = SA :: Lcp(1 + ex[i] + 1, i + ex[i] + 1) + 1;
// cerr << i << " " << ex[i] << " " << lcp << endl;
					// change a[1 + ex[i]] to a[i + ex[i]]
					chg[1 + ex[i]][a[i + ex[i]]] += lcp;
					// change a[i + ex[i]] to a[1 + ex[i]]
					if(1 + ex[i] + lcp >= i + ex[i]) {
// cerr << "? " << endl;
						if(a[i + i + ex[i] - 1] == a[1 + ex[i]]) {
							lcp = i + SA :: Lcp(1 + ex[i] + i, i + ex[i] + i);
						}
						if(a[1 + ex[i]] != a[i + i + ex[i] - 1]) {
							lcp = i - 1;
						}
					}
					chg[i + ex[i]][a[1 + ex[i]]] += lcp;
				}
			}
			else { // have cross
				Sub(i, i + ex[i] - 1, 1);
				Sub(1, i - 1, ex[i] - i + 2);
				int lcp = SA :: Lcp(1 + ex[i] + 1, i + ex[i] + 1) + 1;
// cerr << i << " " << ex[i] << " " << lcp << endl;
				if(1 + ex[i] + lcp >= i + ex[i]) {
// cerr << "? " << endl;
					if(a[i + i + ex[i] - 1] == a[1 + ex[i]]) {
						lcp = i + SA :: Lcp(1 + ex[i] + i, i + ex[i] + i);
					}
					if(a[1 + ex[i]] != a[i + i + ex[i] - 1]) {
						lcp = i - 1;
					}
				}
				chg[i + ex[i]][a[1 + ex[i]]] += lcp;
			}
		}
// for(int i = 1; i <= n; ++ i)
// 	cerr << dif2[i] << " ";
// cerr << endl;
		for(int i = n; i; -- i)
			dif1[i] += dif1[i + 1] + dif2[i];
// for(int i = 1; i <= n; ++ i)
// 	cerr << dif1[i] << " ";
// cerr << endl;
		for(int i = n; i; -- i)
			val[i] += val[i + 1] + dif1[i];
// for(int i = 1; i <= n; ++ i)
// 	cerr << val[i] << " ";
// cerr << endl;
		long long ans = 0;
// cerr << sum << endl;
		for(int i = 1; i <= n; ++ i) {
			int mx = 0;
			for(auto [x, y] : chg[i]) {
// cerr << "Change " << i << " to " << x << " val = " << y << endl;
				mx = max(mx, y);
			}
// cerr << "Pos " << i << ": val = " << val[i] << " ans = " << sum + val[i] + mx << endl;
			ans += (sum + val[i] + mx) ^ i;
		}
		printf("%lld\n", ans);
	}
}