310367: CF1822G1. Magic Triples (Easy Version)

G1. Magic Triples (Easy Version)time limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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

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

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都满足a_i ≤ 10^6。对于一个给定的整数序列a，一个三元组(i, j, k)被称为“神奇”的，如果满足以下条件：

1. 1 ≤ i, j, k ≤ n。
2. i, j, k两两不同。
3. 存在一个正整数b，使得a_i * b = a_j和a_j * b = a_k。

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

注意，整数i, j和k的顺序没有限制。

输入输出数据格式：
输入：
- 第一行包含一个整数t（1 ≤ t ≤ 10^4），表示测试用例的数量。
- 每个测试用例的描述如下：
- 第一行包含一个整数n（3 ≤ n ≤ 2 * 10^5），表示序列的长度。
- 第二行包含n个整数a_1, a_2, a_3, ..., a_n（1 ≤ a_i ≤ 10^6），表示序列a的元素。
- 所有测试用例的n之和不超过2 * 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_i都满足a_i ≤ 10^6。对于一个给定的整数序列a，一个三元组(i, j, k)被称为“神奇”的，如果满足以下条件： 1. 1 ≤ i, j, k ≤ n。 2. i, j, k两两不同。 3. 存在一个正整数b，使得a_i * b = a_j和a_j * b = a_k。 Kolya收到了一个整数序列a作为礼物，并想要计算这个序列的“神奇三元组”的数量。帮助他完成这个任务！ 注意，整数i, j和k的顺序没有限制。 输入输出数据格式： 输入： - 第一行包含一个整数t（1 ≤ t ≤ 10^4），表示测试用例的数量。 - 每个测试用例的描述如下： - 第一行包含一个整数n（3 ≤ n ≤ 2 * 10^5），表示序列的长度。 - 第二行包含n个整数a_1, a_2, a_3, ..., a_n（1 ≤ a_i ≤ 10^6），表示序列a的元素。 - 所有测试用例的n之和不超过2 * 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 ```