#pragma GCC optimize(1, 2, 3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned ll
// #define int ll
#define ls p << 1
#define rs p << 1 | 1
#define lowbit(x) ((x) & (-x))
#define endl '\n'
#define ld long double
#define MULTI_CASES
const int MaxN = 1e6 + 100;
const int INF = 1e9;
int T, N, M, K;
int ans[MaxN];
vector<int> a;
struct SA {
	int sa[MaxN], rk[MaxN], oldrk[MaxN << 1], id[MaxN], key1[MaxN], cnt[MaxN], height[MaxN];
	int st[MaxN][25], logn[MaxN];
	int n;
	void init(vector<int> s1, int _n) {
		n = _n;
		for (int i = 0; i <= max(n + 1, 127); i++) {
			sa[i] = 0;
			rk[i] = 0;
			oldrk[i] = 0;
			cnt[i] = 0;
			key1[i] = 0;
			id[i] = 0;
			height[i] = 0;
		}
		getsa(s1);
		getheight(s1);
	}
	bool cmp(int x, int y, int w) {
		return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
	}
	inline void getsa(vector<int> s) {
		int i, m = 127, p, w;
		// sa[i]琛ㄧず鍚庣紑鎺掑簭绗琲灏忕殑缂栧彿
		// rk[i]琛ㄧず鍚庣紑i鐨勬帓鍚?
		for (i = 1; i <= n; ++i) ++cnt[rk[i] = s[i]];
		for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
		for (i = n; i >= 1; --i) sa[cnt[rk[i]]--] = i;

		for (w = 1;; w <<= 1, m = p) { // m=p 灏辨槸浼樺寲璁℃暟鎺掑簭鍊煎煙
			for (p = 0, i = n; i > n - w; --i) id[++p] = i;
			for (i = 1; i <= n; ++i) 
				if (sa[i] > w) id[++p] = sa[i] - w;
			memset(cnt, 0, sizeof(cnt));
			for (i = 1; i <= n; ++i) ++cnt[key1[i] = rk[id[i]]];
			// 娉ㄦ剰杩欓噷px[i] != i锛屽洜涓簉k娌℃湁鏇存柊锛屾槸涓婁竴杞殑鎺掑悕鏁扮粍

			for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
			for (i = n; i >= 1; --i) sa[cnt[key1[i]]--] = id[i];
			memcpy(oldrk + 1, rk + 1, n * sizeof(int));
			for (p = 0, i = 1; i <= n; ++i) rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p;
			if (p == n) break;
		}
	}
	inline void getheight(vector<int> s){
		// height[i]=lcp(sa[i],sa[i-1])
		int i, k;
		for (i = 1, k = 0; i <= n; ++i) {
			if (rk[i] == 0) continue;
			if (k) --k;
			while (i + k <= n && s[i + k] == s[sa[rk[i] - 1] + k]) ++k;
			height[rk[i]] = k;
		}
	}
	inline void pre() {
		logn[0] = -1;
		for (int i = 1; i < MaxN; i++) logn[i] = logn[i / 2] + 1;
		for (int i = 1; i <= n; i++) st[i][0] = height[i];
		for (int j = 1; j <= 20; j++) {
			int pj = 1 << (j - 1);
			for (int i = 1; i <= n; i++) {
				if (i + pj <= n)
					st[i][j] = min(st[i][j - 1], st[i + pj][j - 1]);
				else
					st[i][j] = st[i][j - 1];
			}
		}
	}
	inline int lcp(int l, int r) {
		if (l == r) return n - l + 1;
		l = rk[l];
		r = rk[r];
		if (l > r) swap(l, r);
		l++;
		int lp = r - l + 1;
		int n = 1 << logn[lp];
		return min(st[l][logn[lp]], st[r - n + 1][logn[lp]]);
	}
} SA;
struct TT {
	int a[MaxN];
	struct Point {
		ll sum, lan;
	} tree[MaxN << 2], ts;
	void js(int p, int x, int y, int z) {
		tree[p].sum += (y - x + 1) * z;
		tree[p].lan += z;
	}
	void pushdown(int p,int l, int r) {
		if (tree[p].lan) {
			int mid = (l + r) >> 1;
			js(ls, l, mid, tree[p].lan);
			js(rs, mid + 1, r, tree[p].lan);
		}
	}
	inline Point pushup(Point L, Point R) {
		Point now = Point();
		now.sum = L.sum + R.sum;
		return now;
	}
	void build(int p, int l, int r) {
		if (l == r) {
			tree[p].sum = a[l];
			tree[p].lan = 0;
			return;
		}
		pushdown(p, l, r);
		int mid = (l + r) >> 1;
		build(ls, l, mid);
		build(rs, mid + 1, r);
		tree[p] = pushup(tree[ls], tree[rs]);
	}
	void change(int p, int l, int r, int x, int y, int z) {
		if (x > y || l > N) return;
		if (l >= x && r <= y) {
			js(p, l, r, z);
			return;
		}
		pushdown(p, l, r);
		int mid = (l + r) >> 1;
		if (mid >= x) change(ls, l, mid, x, y, z);
		if (mid < y) change(rs, mid + 1, r ,x ,y, z);
		tree[p] = pushup(tree[ls], tree[rs]);
	}
	Point query(int p, int l, int r, int x, int y) {
		if (l >= x && r <= y) {
			return tree[p];
		}
		pushdown(p, l, r);
		int mid = (l + r) >> 1;
		if (mid >= x && mid < y) {
			return pushup(query(ls, l, mid, x, y), query(rs, mid + 1, r, x, y));
		}
		if (mid >= x) return query(ls, l, mid, x, y);
		if (mid < y) return query(rs, mid + 1, r, x, y);
		return Point();
	}
} TT;
ll g[MaxN], b[MaxN];
void updata(int l, int r, int k, int d) {
// 	cerr << l << ' ';
// 	cerr << r << ' ';
// 	cerr << k << ' ';
// 	cerr << d << endl;
	if (l > r) return;
	TT.change(1, 1, N, l + 1, r, 1);
	TT.change(1, 1, N, l, l, k);
	TT.change(1, 1, N, r + 1, r + 1, -k - d * (r - l));
}
struct my_hash {
  static uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }

  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
};
unordered_map<int ,ll> mp[MaxN];
int js(int x, int y) {
	int t = SA.lcp(x + 1, y + 1) + 1;
	if (x + t >= y) {
		int len = y - x;
		t = len;
		if (x <= N && y + len <= N && a[x] == a[y + len]) {
			t += SA.lcp(x + len + 1, y + len + 1) + 1;
		}
		return t;
	} else {
		return t;
	}
}
inline void Solve() {
	cin >> N;
	a.assign(N + 1, 0);
	for (int i = 1; i <= N; i++) {
		cin >> a[i];
		mp[i].clear();
	}
	SA.init(a, N);
	SA.pre();
	for (int i = 1; i <= N; i++) {
		g[i] = SA.lcp(1, i);
		// cerr << g[i] << ' ';
	}
	int sum = 0;
	for (int i = 1; i <= N; i++) {
		sum += g[i];
		TT.a[i] = 0;
	}

	TT.a[1] = sum;
	TT.build(1, 1, N);
	for (int i = 1; i <= N; i++) {
		int l = 1, r = g[i];
		int x = i, y = x + g[i] - 1;
		if (i == 1) continue;
		if (r < x) {
			updata(l, r, -g[i], 1);
			updata(x, y, -g[i], 1);
		} else if (x <= r) {
			updata(l, x - 1, -g[i], 1);
			updata(x, y, -g[i], 1);
		}
		// for (int i = 1; i <= N; i++) {
		// 	b[i] = b[i - 1];
		// 	b[i] += TT.query(1, 1, N, i, i).sum;
		// 	cerr << b[i] << ' ';
		// } cerr << endl;
	}
	// updata(1, 2, -2, 1);
	for (int i = 1; i <= N; i++) {
		b[i] = b[i - 1];
		b[i] += TT.query(1, 1, N, i, i).sum;
		// cerr << b[i] << ' ';
	}
	// cerr << endl;
	for (int i = 1; i <= N; i++) {
		int x = g[i] + 1, y = i + g[i];
		if (y <= N && x <= N) mp[x][a[y]] += SA.lcp(x + 1, y + 1) + 1;
		if (x <= N && y <= N) mp[y][a[x]] += js(x, y);
		// cerr << x << ' ';
		// cerr << a[y] << ' ';
		// cerr << y << ' ';
		// cerr << a[x] << endl;
	}
	ll jg = 0;
	for (int i = 1; i <= N; i++) {
		ans[i] = b[i];
		for (auto it : mp[i]) {
			int ts = b[i] + it.second;
			if (ts > ans[i]) {
				ans[i] = ts;
			}
			ans[i] = max(ans[i], ts);
			// cerr << i << ' ';
			// cerr << it.first << ' ';
			// cerr << it.second << endl;
		}
		jg += (1ll * ans[i]) ^ i;
		// cerr << id << ' ';
	}
	// cerr << endl;
	// for (int i = 1; i <= N; i++) {
	// 	cerr << b[i] << ' ';
	// } cerr << endl;
	// for (int i = 1; i <= N; i++) {
	// 	cerr << ans[i] << ' '; 
	// }
	// cerr << endl;
	cout << jg << endl;
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	srand(time(NULL));
#ifdef MULTI_CASES
	int T;
	cin >> T;
	T= min(T,1000); 
	while (T--)
#endif
		Solve();
}