Problem 3D. Summation(equal version)

时间限制：1000ms

空间限制：256MB

题目描述

给定一个长度为 $n$ ，下标从 $1$ 开始的的序列 $a$ ，请计算下列式子的值：
$$\sum_{i = 1} ^ {n} \sum_{j = 1} ^{i} (a_i == a_j)$$
也就是说，你需要计算有多少对二元组 $(i, j)$ ($1 \le i \le j \le n$) 满足 $a_i = a_j$

输入格式

第一行一个正整数 $T$，代表测试数据组数。

对于每一组有两行输入：

第一行一个整数 $n$ ，代表序列 $a$ 的长度。

第二行包含 $n$ 个整数，用空格隔开，代表序列 $a$ 的 $n$ 个数。

输出格式

输出 $T$ 行，每行一个整数，代表该序列要计算式子的结果。

样例输入

3
4
1 1 1 1
3
1 2 3
5
1 2 1 2 1

样例输出

10
3
9

样例解释

对于第三组数据，满足条件的二元组为 $(1, 1)$, $(1, 3)$, $(1, 5)$, $(2, 2)$, $(2, 4)$, $(3, 3)$, $(3, 5)$, $(4, 4)$, $(5, 5)$

数据规模与约定

对于 $60\%$ 的数据，$1 \le T \le 10^3$, $1 \le n \le 10^3$, $n$ 的总和不超过 $10^3$,

对于 $100\%$ 的数据，$1 \le T \le 10^5$, $1 \le n \le 10^5$, $n$ 的总和不超过 $10^5$, 序列中的每个数满足 $-10^9 \le a_i \le 10^9$