魔法三元组（简单版）

时间限制：4s
空间限制：256MB

题目描述

给定一个长度为 $n$ 的正整数序列 $a$。如果有序三元组 $(i,j,k)$ 满足以下条件，就称它为一个魔法三元组：

• $1\le i,j,k\le n$，且三个下标两两不同；
• 存在一个正整数 $b$，使得 $a_i b=a_j$ 且 $a_j b=a_k$。

求魔法三元组的数量。

这里不要求 $i<j<k$，有序三元组的三个位置具有不同含义。公比 $b$ 可以等于 $1$；此时可以选择三个值相同但下标不同的元素。例如，序列 $[6,2,18]$ 中，$(2,1,3)$ 是一个魔法三元组。

输入格式

第一行包含一个整数 $t$，表示测试数据的组数。

每组测试数据的第一行包含一个整数 $n$，表示序列长度。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

对于每组测试数据，输出一个整数，表示魔法三元组的数量。答案不取模。

样例输入 1

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

样例输出 1

6
1
3
0
9
16
45

样例解释

第一组中，值为 $7$ 的三个元素的下标为 $2,3,5$，它们的六种排列分别构成一个魔法三元组。

第二组中，唯一的魔法三元组为 $(2,1,3)$，对应数值为 $2,6,18$，公比为 $3$。

数据范围

• 对于所有数据，满足 $1\le t\le10000$。
• 对于所有数据，满足 $3\le n\le200000$。
• 对于所有数据，满足 $1\le a_i\le1000000$。
• 所有测试组共同满足 $\sum n\le200000$。