题目描述

这是该问题的简单版本。唯一的区别在于，这个版本中$a_i≤10^9$。

对于给定的 $n$ 个整数的序列 $a$，如果三元组 $(i,j,k)$ 同时满足：

• $1≤i,j,k≤n$
• $i,j,k$ 互不相同
• 存在一个正整数 $b$，使得 $a_i·b=a_j$ 且 $a_j·b=a_k$

则称三元组 $(i,j,k)$ 为神奇三元组。

帮助光头强计算这个序列中的神奇三元组的数量。

注意，整数 $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^9)$——序列 $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$ 中有 $6$ 个神奇三元组，分别是 $(2,3,5)，(2,5,3)，(3,2,5)，(3,5,2)，(5,2,3)，(5,3,2)$。

在第二个例子中，序列 $a$ 中有一个神奇三元组，为 $(2,1,3)$。