Problem Description

After finishing the paper Faster Algorithms for Internal Dictionary Queries, Xiaoqingyu and Qiyi Hadron decided to create the following problem.

Let $\text{lcp}(s, t)$ denote the longest common prefix of strings $s = s_1 s_2 \dots s_n$ and $t = t_1 t_2 \dots t_m$, i.e., the largest integer $k$ such that $0 \le k \le \min(n, m)$ and $s_1 s_2 \dots s_k$ equals $t_1 t_2 \dots t_k$.

Xiaoqingyu gives you a non-empty string $s = s_1 s_2 \dots s_n$. Define $f(s) = \sum\limits_{i=1}^{n} \text{lcp}(s, \text{suf}(s, i))$, where $\text{suf}(s, i)$ denotes the suffix of $s$ starting from $s_i$ (i.e., $\text{suf}(s, i) = s_i s_{i+1} \dots s_n$). Note that in this problem, the alphabet contains $n$ letters, not just $26$.

For each $i = 1, 2, \cdots, n$, you need to answer the following query: if you must change $s_i$ to another different character $c$ ($c \ne s_i$), choose the best character $c$ and compute the maximum value of $f(s^{(i)})$, where $s^{(i)} = s_1 \dots s_{i-1} c s_{i+1} \dots s_n$.

Input Format

There are multiple test cases. The first line contains an integer $T$ denoting the number of test cases. For each test case:

The first line contains an integer $n$ ($2 \le n \le 2 \times 10^5$), the length of the string.

The second line contains $n$ integers $s_1, s_2, \dots, s_n$ ($1 \le s_i \le n$), where $s_i$ means the $i$-th character of the string is the $s_i$-th letter in the alphabet.

It is guaranteed that the sum of all $n$ over the test cases does not exceed $2 \times 10^5$.

Output Format

Let $m(i)$ denote the maximum value of $f(s^{(i)})$. To reduce the output size, for each test case output one integer on a single line, which is $\sum\limits_{i=1}^{n} (m(i) \oplus i)$, where $\oplus$ is the bitwise XOR operator.

2
4
2 1 1 2
12
1 1 4 5 1 4 1 9 1 9 8 10

15
217

Hint

For the first sample, we first compute $m(1)$.

• If we change $s_1$ to $1$, then $f(s^{(1)}) = 4 + 2 + 1 + 0 = 7$.
• If we change $s_1$ to $3$ or $4$, then $f(s^{(1)}) = 4 + 0 + 0 + 0 = 4$.

Therefore, $m(1) = 7$.

Similarly, $m(2) = 6$, $m(3) = 6$, and $m(4) = 4$. So the answer is $(7 \oplus 1) + (6 \oplus 2) + (6 \oplus 3) + (4 \oplus 4) = 15$.

Translated by ChatGPT 5