Magic Triples (Easy Version) solution codeforces

This is the easy version of the problem. The only difference is that in this version, $a_{i} \leq 10^{6}$ .

For a given sequence of $n$ integers $a$ , a triple $(i, j, k)$ is called magic if:

$1 \leq i, j, k \leq n$ .
$i$ , $j$ , $k$ are pairwise distinct.
there exists a positive integer $b$ such that $a_{i} \cdot b = a_{j}$ and $a_{j} \cdot b = a_{k}$ .

Kolya received a sequence of integers $a$ as a gift and now wants to count the number of magic triples for it. Help him with this task!

Note that there are no constraints on the order of integers $i$ , $j$ and $k$ .

Input

The first line contains a single integer $t$ ( $1 \leq t \leq 10^{4}$ ) — the number of test cases. The description of the test cases follows.

The first line of the test case contains a single integer $n$ ( $3 \leq n \leq 2 \cdot 10^{5}$ ) — the length of the sequence.

The second line of the test contains $n$ integers $a_{1}, a_{2}, a_{3}, \dots, a_{n}$ ( $1 \leq a_{i} \leq 10^{6}$ ) — the elements of the sequence $a$ .

The sum of $n$ over all test cases does not exceed $2 \cdot 10^{5}$ .

Output

For each test case, output a single integer — the number of magic triples for the sequence $a$ .

Example

1 7 7 2 7

6 2 18

1 2 3 4 5 6 7 8 9

1000 993 986 179

1 10 100 1000 10000 100000 1000000

1 1 2 2 4 4 8 8

1 1 1 2 2 2 4 4 4

Note

In the first example, there are $6$ magic triples for the sequence $a$ — $(2, 3, 5)$ , $(2, 5, 3)$ , $(3, 2, 5)$ , $(3, 5, 2)$ , $(5, 2, 3)$ , $(5, 3, 2)$ .

In the second example, there is a single magic triple for the sequence $a$ — $(2, 1, 3)$ .

Leave a Comment Cancel reply