你有 $$$n$$$ 棍子,编号从 $$$1$$$ 到 $$$n$$$。第 $$$i$$$ 根棍子的长度为 $$$2^{a_i}$$$。
您想要从给定的 $$$n$$$ 棒中准确选择 $$$3$$$ 棒,并使用这些棒作为三角形的边,用它们形成一个非退化三角形。如果三角形的面积严格大于 $$$0$$$,则该三角形称为非退化三角形。
你必须计算精确选择 $$$3$$$ 棍子的方法数,以便可以用它们形成三角形。请注意,选择棒的顺序并不重要(例如,选择 $$$1$$$-st、$$$2$$$-nd 和 $$$4$$$-th 棒与选择 $$$2$$$-nd、$$$4$$$-th 和 $$$1$$$-st 棒相同)。
输入
第一行包含一个整数 $$$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$$$ 棒的方法数量,以便可以用它们形成一个三角形。
示例
输入 #1
4 7 1 1 1 1 1 1 1 4 3 2 1 3 3 1 2 3 1 1
输出 #1
35 2 0 0
注意
在示例的第一个测试用例中,可以选择给定的 $$$7$$$ 中的任意三个棍子。
在示例的第二个测试用例中,您可以选择 $$$1$$$-st、$$$2$$$-nd 和 $$$4$$$-th 棒,或者 $$$1$$$-st、$$$3$$$-rd 和 $$$4$$$-th 棒。
在示例的第三个测试用例中,您无法用长度为 $$$2$$$、$$$4$$$ 和 $$$8$$$ 的给定木棍形成三角形。