#include <bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); i--)
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

VI zFunction(const VI& s)
{
	int n = SZ(s);
	VI z(n);
	
	int l = 0;
	int r = 0;
	FOR (i, 1, n)
	{
		z[i] = 0;
		if (i <= r)
			z[i] = min(r - i + 1, z[i - l]);
		
		while (i + z[i] < n && s[i + z[i]] == s[z[i]])
			z[i]++;
		if (i + z[i] - 1 > r)
		{
			r = i + z[i] - 1;
			l = i;
		}
	}
	return z;
}
void countSort(VI& p, const VI& c)
{
	int n = SZ(p);
	VI cnt(n);
	FOR (i, 0, n)
		cnt[c[i]]++;
	VI pos(n);
	FOR (i, 1, n)
		pos[i] = pos[i - 1] + cnt[i - 1];
	VI p2(n);
	for (auto x : p)
	{
		int i = c[x];
		p2[pos[i]++] = x;
	}
	p = p2;
}

VI suffixArray(VI s)
{
	int n = SZ(s);
	// strictly smaller than any other element
	s.PB(-1);
	n++;
	VI p(n), c(n);
	iota(ALL(p), 0);
	sort(ALL(p), [&](int i, int j)
	{
		return s[i] < s[j];
	});
	int x = 0;
	c[p[0]] = 0;
	FOR (i, 1, n)
	{
		if (s[p[i]] != s[p[i - 1]])
			x++;
		c[p[i]] = x;
	}
	int k = 0;
	while ((1 << k) < n)
	{
		FOR (i, 0, n)
			p[i] = (p[i] - (1 << k) + n) % n;
		countSort(p, c);
		VI c2(n);
		PII pr = {c[p[0]], c[(p[0] + (1 << k)) % n]};
		FOR (i, 1, n)
		{
			PII nx = {c[p[i]], c[(p[i] + (1 << k)) % n]};
			c2[p[i]] = c2[p[i - 1]];
			if (pr != nx)
				c2[p[i]]++;
			pr = nx;
		}
		c = c2;
		k++;
	}
	p.erase(p.begin());
	s.pop_back();
	n--;
	return p;
}

const int LOG = 19;
const int INF = 1e9 + 7;

struct SparseTable
{
	VI t[LOG];
	
	void push_back(int v)
	{
		int i = SZ(t[0]);
		t[0].PB(v);
		FOR (j, 0, LOG - 1) 
			t[j + 1].PB(min(t[j][i], t[j][max(0, i - (1 << j))]));
	}
	// [l, r)
	int query(int l, int r)
	{
		assert(l < r && r <= SZ(t[0]));
		int i = 31 - __builtin_clz(r - l);
		return min(t[i][r - 1], t[i][l + (1 << i) - 1]);
	}
};

struct LCP
{
	int n;
	VI s, sa, rnk, lcp;
	SparseTable st;

	LCP(VI _s): n(SZ(_s)), s(_s)
	{
		sa = suffixArray(s);
		rnk.resize(n);
		FOR (i, 0, n)
			rnk[sa[i]] = i;
		lcpArray();
		FOR (i, 0, n - 1)
			st.PB(lcp[i]);
	}

	void lcpArray()
	{
		lcp.resize(n - 1);
		int h = 0;
		FOR (i, 0, n)
		{
			if (h > 0)
				h--;
			if (rnk[i] == 0)
				continue;
			int j = sa[rnk[i] - 1];
			for (; j + h < n && i + h < n; h++)
			{
				if (s[j + h] != s[i + h])
					break;
			}
			lcp[rnk[i] - 1] = h;
		}
	}
	int queryLcp(int i, int j)
	{
		if (i == n || j == n)
			return 0;
		assert(i != j); // return n - i ????
		i = rnk[i];
		j = rnk[j];
		if (i > j)
			swap(i, j);
		// query [i, j)
		return st.query(i, j);
	}
};
struct Fenwick
{
	int n;
	vector<LL> t;
	
	Fenwick(int _n = 0): n(_n), t(n, 0) {}
	
	void upd(int i, LL x)
	{
		for (; i < n; i |= i + 1)
			t[i] += x;
	}
	LL query(int i)
	{
		LL ans = 0;
		for (; i >= 0; i = (i & (i + 1)) - 1)
			ans += t[i];
		return ans;
	}
	LL query(int l, int r)
	{
		return query(r) - query(l - 1);
	}
};

void solve()
{
	int n;
	cin >> n;
	VI v(n);
	FOR (i, 0, n)
		cin >> v[i];
		
	VI z = zFunction(v);
	VI sa = suffixArray(v);
	LCP lcp(v);
	
	vector<LL> ans(n, n + accumulate(ALL(z), 0ll));
	
	// PART MINUS A
	{
		LL minusA = 0, cntA = 0;
		vector<VI> events(n + 1);
		FOR (j, 1, n)
		{
			events[j].PB(j + z[j]);
			events[j + z[j]].PB(-(j + z[j]));
		}
		FOR (i, 0, n)
		{
			for (auto e : events[i])
			{
				minusA += e;
				if (e < 0)
					cntA--;
				else
					cntA++;
			}
			ans[i] -= minusA - cntA * i;
		}
	}
	
	// PART MINUS B
	{
		Fenwick cnt(n), sum(n);
		
		FOR (j, 1, n)
		{
			cnt.upd(z[j], 1);
			sum.upd(z[j], z[j]);	
		}
		FOR (i, 0, n)
		{
			if (i)
			{
				cnt.upd(z[i], -1);
				sum.upd(z[i], -z[i]);
			}
			LL cntB = cnt.query(i, n);
			LL sumB = sum.query(i, n);
			
			ans[i] -= sumB - cntB * i;
		}
	}
	
	//FOR(i, 0, n)
	//	cerr << ans[i] << " ";
	//cerr << endl;
	// PART PLUS
	{
		vector<VI> eventsA(n + 1);
		vector<VI> eventsB(n + 1);
		FOR (j, 1, n)
		{
			eventsA[z[j]].PB(j);
			eventsB[j + z[j]].PB(j);
		}
		FOR (i, 0, n)
		{
			map<int, LL> mp;
			//PLUS A
			for (auto j : eventsA[i])
			{
				if (j + z[j] == n || j <= i)
					continue;
				int c = v[j + z[j]];
				if(c == v[i])
					continue;
				int add = lcp.queryLcp(i + 1, j + z[j] + 1) + 1;
				mp[c] += add;
			}
			//cerr << mp[3] << endl;
			//PLUS B
			for (int j : eventsB[i])
			{
				int c = v[z[j]];
				if(c == v[i])
					continue;
				int len = lcp.queryLcp(z[j] + 1, i + 1);
				if (z[j] + len + 1 == i && j + i < n && v[j + i] == c)
					len = i + lcp.queryLcp(i + 1, j + i + 1) + 1;
				else
					len = min(i, z[j] + 1 + len);
				
				int add = len - z[j];
				mp[c] += add;
			}
			LL mx = 0;
			for (auto [c, val] : mp)
			{
				mx = max(mx, val);
			}
			ans[i] += mx;
		}
	}
	LL res = 0;
	FOR (i, 0, n)
	{
		//cerr << ans[i] << " ";
		res += (i + 1) ^ ans[i];
	}
	//cerr << endl;
	cout << res << '\n';
	
	
}

int main()
{
	ios::sync_with_stdio(0); 
	cin.tie(0);
	cout << fixed << setprecision(15);
	
	int t;
	cin >> t;
	while (t--)
	{
		solve();
	}
	
	
	return 0;
}