G. Count the squares
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given $$$n$$$ squares, where the side length of the $$$i$$$-th square is $$$a_i$$$.

Your task is to count the number of triples $$$(i, j, k)$$$ where ($$$1 \le i \lt j \lt k \le n$$$) such that the three squares at indices $$$i, j,$$$ and $$$k$$$ can be arranged to form a rectangle without any gaps or overlaps.

A square is considered a special case of a rectangle.

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 2\cdot 10^5$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2\cdot 10^5$$$) — the number of squares.

The second line contains $$$n$$$ space-separated integers $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$) — the side length of each square.

It is guaranteed that the sum of $$$n$$$ over all test cases will not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print a single integer — the number of triples of squares that can form a rectangle.

Example
Input
2
5
3 3 3 3 5
4
1 2 3 4
Output
4
0
Note

In the first test case, the possible triples are: $$$(1, 2, 3)$$$, $$$(1, 2, 4)$$$, $$$(1, 3, 4)$$$, $$$(2, 3, 4)$$$.