学校里的体育比赛有时会变得过于激烈。为了促进合作，老师们设计了一个游戏，通过合作可以获得更高的分数。

这个合作游戏开始时有 $N$ 名学生排成一列。为了得分，两名来自同一个班级的学生将离开队伍。如果他们在离开队伍前分别是队列中的第 $i$ 位和第 $j$ 位学生，他们会将 $|i - j|$ 加到总分中。这两名学生离开后，留下的空位会被压缩。当队伍中不再有来自同一个班级的学生对时，游戏结束。

例如，考虑最初排成一列的六名学生： $1, 2, 3, 3, 2, 1$

这些数字是学生的班级编号。如果学生按照班级编号 $1$、然后是班级编号 $2$、最后是班级编号 $3$ 的顺序离开队伍，总分为 $5 + 3 + 1 = 9$。然而，在相同的初始情况下，如果学生按照 $3, 2, 1$ 的顺序离开，总分为 $1 + 1 + 1 = 3$。

给定初始队列中的班级编号，编写一个程序来计算可能的最大总分。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量 ($1 \le T \le 48$)。接下来是各测试用例。 每个测试用例的第一行包含一个整数 $N$，表示学生人数 ($1 \le N \le 300\,000$)。 下一行给出了班级编号序列。班级编号是 $1$ 到 $N$ 之间的整数。 所有测试用例的 $N$ 之和不超过 $7\,000\,000$。

输出格式

对于每个测试用例，输出一行，包含一个整数：可能的最大总分。

样例

样例输入 1

2
7
1 2 1 1 2 1 2
12
1 2 3 1 2 3 1 2 3 1 2 3

样例输出 1

10
30