#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;
}
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)]);
}
} st;
VI rnk;
VI lcpArray(const VI& s, const VI& sa)
{
int n = SZ(s);
rnk.resize(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;
}
int queryLcp(int i, int j)
{
if (i == SZ(rnk) || j == SZ(rnk))
return 0;
i = rnk[i];
j = rnk[j];
if (i > j)
swap(i, j);
assert(i != j);
return st.query(i, j);
}
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);
st.init(SZ(v));
st.build(lcp);
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 || j <= i)
continue;
int c = v[j + z[j]];
if(c == v[i])
continue;
int add = 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 = 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 [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;
}