#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(const VI& t)
{
	VI s = t;
	s.PB(-1);
	
	
	int n = SZ(s);
	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());
	return p;
}

VI lcpArray(const VI& s, const VI& sa)
{
	int n = SZ(s);
	VI rnk(n);
	FOR (i, 0, n)
		rnk[sa[i]] = i;
	VI lcp(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;
	}
	return lcp;
}

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

struct SparseTable
{
	VI t[LOG];
	VI lg;
	int n;
	
	void init(int _n)
	{
		n = _n;
		lg.resize(n + 1);
		FOR (i, 2, n + 1)
			lg[i] = lg[i / 2] + 1;
		FOR (j, 0, LOG)
			t[j].assign(n, INF);
	}
	
	void build(const VI& v)
	{
		FOR (i, 0, SZ(v)) t[0][i] = v[i];
		
		FOR (j, 1, LOG)
		{
			int len = 1 << (j - 1);
			FOR (i, 0, n - (1 << j) + 1)
			{
				t[j][i] = min(t[j - 1][i], t[j - 1][i + len]);
			}
		}
	}
	
	int query(int l, int r)
	{
		int i = lg[r - l];
		return min(t[i][l], t[i][r - (1 << i)]);
	}
};


struct Fenwick
{
	int n;
	vector<LL> v;
	
	void init(int _n)
	{
		n = _n;
		v.clear();
		v.assign(n, 0);
	}
	
	void upd(int i, LL x)
	{
		for (; i < n; i |= (i + 1))
			v[i] += x;
	}
	
	LL query(int i)
	{
		LL ans = 0;
		for (; i >= 0; i = (i & (i + 1)) - 1)
			ans += v[i];
		return ans;
	}
	
	// [l, r)
	LL query(int l, int r)
	{
		return query(r - 1) - 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);
	VI p(n);
	FOR (i, 0, n)
		p[sa[i]] = i;
	VI lcp = lcpArray(v, sa);
	SparseTable st;
	st.init(SZ(v));
	st.build(lcp);
	
	auto queryLcp = [&](int i, int j)
	{
		if (i == n || j == n)
			return 0;
		i = p[i];
		j = p[j];
		if (i > j)
			swap(i, j);
		assert(i != j);
		return st.query(i, j);
	};
	
	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, sum;
		cnt.init(n);
		sum.init(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)
					continue;
				int c = v[j + z[j]];
				int add = queryLcp(i + 1, j + z[j] + 1) + 1;
				mp[c] += add;
			}
			//PLUS B
			for (int j : eventsB[i])
			{
				int c = v[z[j]];
				int len = queryLcp(z[j] + 1, i + 1);
				if (z[j] + len + 1 == i && j + i < n && v[j + i] == c)
					len = i + 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 [_, 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;
}