#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mkp make_pair
#define pb push_back
typedef pair <int, int> pii;
typedef long long LL;

inline int read() {
	int x = 0, f = 0;
	char c = getchar();
	while (!isdigit(c)) {if (c == '-') f = 1; c = getchar();}
	while (isdigit(c)) x = (x << 1) + (x << 3) + (c & 15), c = getchar();
	return f? -x : x;
}

const int MAXN = 2e5;
namespace ST {
	const int MAXST = MAXN*2;
	template <class T1>
		struct ST {
			T1 mn[21][MAXST];
			void build(T1 *a, int n) {
				for (int i = 1; i <= n; ++i) mn[0][i] = a[i - 1];
				for (int j = 1; j <= 20; ++j)
					for (int i = 1; i + (1 << j - 1) <= n; ++i)
						mn[j][i] = min(mn[j - 1][i], mn[j - 1][i + (1 << j - 1)]);
			}
			T1 query(int l, int r) {
				int k = 31 - __builtin_clz(r - l + 1);
				return min(mn[k][l], mn[k][r - (1 << k) + 1]);
			}
		};
}

namespace SAM {
	const int MAXS = MAXN*2;
	struct SAM {
		vector <int> G[MAXS];
	//	int ch[MAXS][28];
		map <int, int> ch[MAXS];
		int len[MAXS], siz[MAXS], fa[MAXS], last, tot;
		int extend(int c) {
			int np = ++tot, p = last; last = np;
			len[np] = len[p] + 1; siz[np] = 1;
			for (; p && ch[p].find(c) == ch[p].end(); p = fa[p]) ch[p][c] = np;
			if (ch[p].find(c) == ch[p].end()) {
				ch[p][c] = np;
				fa[np] = p;
				return np;
			}
			int q = ch[p][c];
			if (len[q] > len[p] + 1) {
				int nq = ++tot; len[nq] = len[p] + 1; fa[nq] = fa[q];
				//for (int i = 0; i < 26; ++i) ch[nq][i] = ch[q][i];
				ch[nq] = ch[q];
				fa[np] = fa[q] = nq;
				for (; ch[p].find(c) != ch[p].end() && ch[p][c] == q; p = fa[p]) ch[p][c] = nq;
			}
			else fa[np] = q;
			return np;
		}

		ST :: ST<pii> st;
		int dfn[MAXS], tt;
		void dfs(int x, int dep) {
			dfn[x] = ++tt;
			for (auto v : G[x]) {
				dfs(v, dep + 1);
				siz[x] += siz[v];
			}
		}
		pii a_[MAXS];
		void build() {
			for (int i = 1; i <= tot; ++i)
				G[fa[i]].pb(i);
			dfs(0, 0);
			for (int i = 0; i <= tot; ++i) a_[dfn[i]] = mkp(dfn[fa[i]], fa[i]);
			st.build(a_ + 1, tot + 1);
		}
		void clear() {
	//		st.clear();
			for (int i = 0; i <= tot + 1; ++i) {
				//memset(ch[i], 0, sizeof(ch[i]));
				ch[i].clear();
				len[i] = siz[i] = fa[i] = 0;
				G[i].clear();
			}
			tt = last = tot = 0;
		}
		int LCA(int x, int y) {
			if (x == y) return x;
			if (dfn[x] > dfn[y]) swap(x, y);
			return st.query(dfn[x] + 1, dfn[y]).se;
		}
		inline int LCP(int x, int y) {return len[LCA(x, y)];} //front
	};
}
SAM :: SAM s1;
int pos[MAXN + 10], s[MAXN + 10], len[MAXN + 10];

unordered_map <int, int> mp;
map <int, LL> exc[MAXN + 10];
vector <int> vec[MAXN + 10];

LL c1[MAXN + 10], v1[MAXN + 10], res[MAXN + 10], ans[MAXN + 10];
int main() {
	int T = read();
	while (T--) {
		int n = read();
		for (int i = 1; i <= n; ++i) s[i] = read();
		for (int i = n; i >= 1; --i) {
			pos[i] = s1.extend(s[i]);
		}
		s1.build();
		LL ans = 0, sum = 0, cnt = 0;
		for (int i = 2; i <= n; ++i) {
			len[i] = s1.LCP(pos[1], pos[i]);
			ans += len[i];

			c1[1]++;
			c1[min(len[i] + 1, i)]--;
			res[1] -= len[i]; 
			res[min(len[i] + 1, i)] += len[i];

			c1[i]++;
			c1[i + len[i]]--;
			v1[i] -= i - 1;
			v1[i + len[i]] += i - 1;
			res[i] -= len[i];
			res[len[i] + i] += len[i];
			//vec[i + len[i]].pb(i);
			int l1 = s1.LCP(pos[i + len[i] + 1], pos[1 + len[i] + 1]) + 1;
		//	cerr << l1 << " ";
			if (1 + len[i] < i)
				exc[1 + len[i]][s[i + len[i]]] += l1;
			if (l1 + len[i] >= i + len[i]) {
				//l1 + len[i] ->  i + len[i];
				l1 = i - 1;
			}
			else {
				int tmp = s[i + len[i]]; s[i + len[i]] = s[1 + len[i]];
				if (l1 + len[i] == i + len[i] - 1 && s[1 + l1 + len[i]] == s[i + len[i] + l1]) {
					l1 += 1 + s1.LCP(pos[l1 + len[i] + 2], pos[i + len[i] + l1 + 1]);
				}
				s[i + len[i]] = tmp;
			}
	//		cerr << l1 << endl;
			exc[i + len[i]][s[1 + len[i]]] += l1;
/*
			if (i + len[i] == 5) {
				cerr << "sss";
			}*/
			/*
			if (i + len[i] == 4 && s[1 + len[i]] == 1) {
				cout << i << " " << l1 << endl;
			}*/
		}
	//	cerr << ans << endl;
		LL rnm = 0; ans += n;
		for (int i = 1; i <= n; ++i) {
			sum += res[i];
			cnt += c1[i];
			sum += v1[i];
			LL mx = 0;
			for (auto v : exc[i])
				mx = max(mx, v.se);
			::ans[i] = mx + ans + sum + cnt * (i - 1);
	//		cerr << ::ans[i] << " ";
			rnm += ::ans[i] ^ i;
		}
	//	cerr << endl;
	//	cerr << endl;
		printf("%lld\n", rnm);
		for (int i = 1; i <= n + 1; ++i) {
			exc[i].clear();
			c1[i] = v1[i] = res[i] = 0;
		}
		s1.clear();
	}
	return 0;
}