时间限制：1秒　　内存限制：256M

---

【问题描述】

　　有 \(n\) 个带颜色的方块排成一列，相同颜色的方块连成一个区域。

　　游戏时，可以任选一个区域消去。设这个区域包含的方块数为 \(x\)，则将得到 \(x^2\) 的分值，之后右边所有方块会向左靠，直到与左边的方块挨着或到最左边。

　　你的任务是求出可能得到的最高分。

【输入格式】

　　第一行包含测试的次数 \(t\) 。每个次测试的输入包含两行：第一行包含整数\(n\)，即方块数，第二行包含 \(n\) 个数，代表每个方块的颜色。数字的大小 \(1..n\) 内。

【输出格式】

　　每次测试输出一个整数，表示最大得分。

【输入输出样例】

　Input

3
9
1 2 2 2 2 3 3 3 1
1
8
24
5 1 1 2 2 5 1 5 3 2 1 2 3 3 3 2 2 1 1 3 3 1 1 5

　Output

29
8
98

【数据限制】

　　\(100\%\) 的数据：\(1≤t≤50，1≤n≤200\)。

【来源】

　Mr.he