Sherlock is given an array of \(N\) integers (\(A_0, A_1 \dots A_{N-1}\)) by Watson. Now Watson asks Sherlock how many different pairs of indices \(i\) and \(j\) exist such that \(i\) is not equal to \(j\) but \(A_i\) is equal to \(A_j\).

That is, Sherlock has to count the total number of pairs of indices \((i,j)\) where \(A_i=A_j\) and \(i\neq j\).

## Input Format

The first line contains \(T\), the number of test cases. \(T\) test cases follow.

Each test case consists of two lines; the first line contains an integer \(N\), the size of array, while the next line contains \(N\) space separated integers.

## Output Format

For each test case, print the required answer on a different line.

## Constraints

- \(1\leq T \leq 10\)
- \(1\leq N\leq 10^5\)
- \(1\leq A[i]\leq 10^6\)

## Solution

The easiest solution for this problem is an \(O(n^2)\) algorithm, that loops over the array twice and checks if the condition \(A_i=A_j\) and \(i\neq j\) holds for each pair \((i, j)\):

```
function solve(a) {
let c = 0;
for (let i = 0; i < a.length; i++) {
for (let j = 0; j < a.length; j++) {
if (i !== j && a[i] == a[j]) {
c++;
}
}
}
return c;
}
```

While this algorithm works for the first test cases, it fails later since the constraints state that the number of elements in the array can contain up to \(10^5\) elements.

But if we count each element in the array, we know that for each unique value \(k\) in the array and its count \(c_k\), exactly \(c_k^2 - c_k\) elements are possible, as it is a full permutation reduced by the number of occurences for \(i=j\). So, an \(O(n)\) solution can be found by storing all elements of the array in a hashmap and then sum over all unique numbers:

\[\sum_{k\in A} c_k(c_k - 1)\]

An implementation can then be stated like this:

```
function solve(a) {
let s = 0, c = {};
for (let i = 0; i < a.length; i++) {
c[a[i]] = (c[a[i]] || 0) + 1;
}
for (let k in c) {
s+= c[k] * c[k] - c[k];
}
return s;
}
```

This solution has a space complexity of \(O(n)\). When we sort the array in-place first in \(O(n\log n)\), we can then solve the problem in \(O(n)\) with \(O(1)\) additional space requirements:

```
function solve(a) {
a.sort((x, y) => x - y);
let s = 0, c = 1, p = a[0];
for (let i = 1; i < a.length; i++) {
if (a[i] == p) {
c++;
} else {
s+= c * c - c;
c = 1;
}
p = a[i];
}
return s + c * c - c;
}
```