Description:
The weight of a sequence is defined as the number of unordered pairs of indexes $$$(i,j)$$$ (here $$$i \lt j$$$) with same value ($$$a_{i} = a_{j}$$$). For example, the weight of sequence $$$a = [1, 1, 2, 2, 1]$$$ is $$$4$$$. The set of unordered pairs of indexes with same value are $$$(1, 2)$$$, $$$(1, 5)$$$, $$$(2, 5)$$$, and $$$(3, 4)$$$.
You are given a sequence $$$a$$$ of $$$n$$$ integers. Print the sum of the weight of all subsegments of $$$a$$$.
A sequence $$$b$$$ is a subsegment of a sequence $$$a$$$ if $$$b$$$ can be obtained from $$$a$$$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.
Input Format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). Description of the test cases follows.
The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$).
The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.
Output Format:
For each test case, print a single integer — the sum of the weight of all subsegments of $$$a$$$.
Note:
- In test case $$$1$$$, all possible subsegments of sequence $$$[1, 2, 1, 1]$$$ having size more than $$$1$$$ are: $$$[1, 2]$$$ having $$$0$$$ valid unordered pairs; $$$[2, 1]$$$ having $$$0$$$ valid unordered pairs; $$$[1, 1]$$$ having $$$1$$$ valid unordered pair; $$$[1, 2, 1]$$$ having $$$1$$$ valid unordered pairs; $$$[2, 1, 1]$$$ having $$$1$$$ valid unordered pair; $$$[1, 2, 1, 1]$$$ having $$$3$$$ valid unordered pairs. Answer is $$$6$$$.
- In test case $$$2$$$, all elements of the sequence are distinct. So, there is no valid unordered pair with the same value for any subarray. Answer is $$$0$$$.