310368: CF1822G2. Magic Triples (Hard Version)

G2. Magic Triples (Hard Version)time limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

This is the hard version of the problem. The only difference is that in this version, $a_i \le 10^9$.

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

• $1 \le i, j, k \le 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 \le t \le 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 \le n \le 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 \le a_i \le 10^9$) — 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$.

ExampleInput

7
5
1 7 7 2 7
3
6 2 18
9
1 2 3 4 5 6 7 8 9
4
1000 993 986 179
7
1 10 100 1000 10000 100000 1000000
8
1 1 2 2 4 4 8 8
9
1 1 1 2 2 2 4 4 4

Output

6
1
3
0
9
16
45

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)$.

题目大意：
这是一个难题的较难版本。在这个版本中，唯一的区别是 $a_i \le 10^9$。

对于给定的一个整数序列 $a$，一个三元组 $(i, j, k)$ 被称为“魔法”的，如果满足以下条件：
1. $1 \le i, j, k \le n$。
2. $i$、$j$、$k$ 两两不同。
3. 存在一个正整数 $b$，使得 $a_i \cdot b = a_j$ 和 $a_j \cdot b = a_k$。

Kolya 收到了一个整数序列 $a$ 作为礼物，并想要计算这个序列的“魔法”三元组的数量。帮助他完成这个任务！

注意，$i$、$j$ 和 $k$ 的顺序没有限制。

输入输出数据格式：
输入：
- 第一行包含一个整数 $t$（$1 \le t \le 10^4$）——测试用例的数量。
- 每个测试用例的描述如下：
- 第一行包含一个整数 $n$（$3 \le n \le 2 \cdot 10^5$）——序列的长度。
- 第二行包含 $n$ 个整数 $a_1, a_2, a_3, \dots, a_n$（$1 \le a_i \le 10^9$）——序列 $a$ 的元素。
- 所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出：
- 对于每个测试用例，输出一个整数——序列 $a$ 的“魔法”三元组的数量。

示例：
输入：
```
7
5
1 7 7 2 7
3
6 2 18
9
1 2 3 4 5 6 7 8 9
4
1000 993 986 179
7
1 10 100 1000 10000 100000 1000000
8
1 1 2 2 4 4 8 8
9
1 1 1 2 2 2 4 4 4
```
输出：
```
6
1
3
0
9
16
45
```

注意：
- 在第一个示例中，序列 $a$ 有 6 个“魔法”三元组——$(2, 3, 5)$, $(2, 5, 3)$, $(3, 2, 5)$, $(3, 5, 2)$, $(5, 2, 3)$, $(5, 3, 2)$。
- 在第二个示例中，序列 $a$ 有一个“魔法”三元组——$(2, 1, 3)$。题目大意： 这是一个难题的较难版本。在这个版本中，唯一的区别是 $a_i \le 10^9$。 对于给定的一个整数序列 $a$，一个三元组 $(i, j, k)$ 被称为“魔法”的，如果满足以下条件： 1. $1 \le i, j, k \le n$。 2. $i$、$j$、$k$ 两两不同。 3. 存在一个正整数 $b$，使得 $a_i \cdot b = a_j$ 和 $a_j \cdot b = a_k$。 Kolya 收到了一个整数序列 $a$ 作为礼物，并想要计算这个序列的“魔法”三元组的数量。帮助他完成这个任务！ 注意，$i$、$j$ 和 $k$ 的顺序没有限制。 输入输出数据格式： 输入： - 第一行包含一个整数 $t$（$1 \le t \le 10^4$）——测试用例的数量。 - 每个测试用例的描述如下： - 第一行包含一个整数 $n$（$3 \le n \le 2 \cdot 10^5$）——序列的长度。 - 第二行包含 $n$ 个整数 $a_1, a_2, a_3, \dots, a_n$（$1 \le a_i \le 10^9$）——序列 $a$ 的元素。 - 所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。 输出： - 对于每个测试用例，输出一个整数——序列 $a$ 的“魔法”三元组的数量。 示例： 输入： ``` 7 5 1 7 7 2 7 3 6 2 18 9 1 2 3 4 5 6 7 8 9 4 1000 993 986 179 7 1 10 100 1000 10000 100000 1000000 8 1 1 2 2 4 4 8 8 9 1 1 1 2 2 2 4 4 4 ``` 输出： ``` 6 1 3 0 9 16 45 ``` 注意： - 在第一个示例中，序列 $a$ 有 6 个“魔法”三元组——$(2, 3, 5)$, $(2, 5, 3)$, $(3, 2, 5)$, $(3, 5, 2)$, $(5, 2, 3)$, $(5, 3, 2)$。 - 在第二个示例中，序列 $a$ 有一个“魔法”三元组——$(2, 1, 3)$。