B. 组成三角形

时间限制：每个测试 $2$ 秒
内存限制：每个测试 $256$ MB

你有 $n$ 根棍子，编号从 $1$ 到 $n$。第 $i$ 根棍子的长度为 $2^{a_i}$。

你想从给定的 $n$ 根棍子中恰好选出 $3$ 根，并用它们作为三角形的三条边组成一个非退化三角形。若一个三角形的面积严格大于 $0$，则称其为非退化三角形。

你需要计算有多少种选出 $3$ 根棍子的方案，使得它们能组成一个三角形。注意选取棍子的顺序无关紧要（例如，选择第 $1$、$2$ 和 $4$ 根棍子与选择第 $2$、$4$ 和 $1$ 根棍子视为同一种方案）。

输入

第一行包含一个整数 $t$（$1 \le t \le 10^4$）——测试用例的数量。

每个测试用例包含两行：

• 第一行包含一个整数 $n$（$1 \le n \le 3 \cdot 10^5$）；
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le n$）。

输入的附加限制：所有测试用例的 $n$ 之和不超过 $3 \cdot 10^5$。

输出

对于每个测试用例，输出一个整数——能组成三角形的选出 $3$ 根棍子的方案数。

样例

输入

4
7
1 1 1 1 1 1 1
4
3 2 1 3
3
1 2 3
1
1

输出

35
2
0
0

说明

在第一个测试用例中，给定 $7$ 根棍子中的任意 $3$ 根都可以被选出组成三角形。

在第二个测试用例中，你可以选择第 $1$、$2$ 和 $4$ 根棍子，或者第 $1$、$3$ 和 $4$ 根棍子。

在第三个测试用例中，无法用长度为 $2$、$4$ 和 $8$ 的棍子组成三角形。