题目描述
这是该问题的简单版本。唯一的区别在于,这个版本中ai≤109。
对于给定的 n 个整数的序列 a,如果三元组 (i,j,k) 同时满足:
- 1≤i,j,k≤n
- i,j,k 互不相同
- 存在一个正整数 b,使得 ai⋅b=aj 且 aj⋅b=ak
则称三元组 (i,j,k) 为神奇三元组。
帮助光头强计算这个序列中的神奇三元组的数量。
注意,整数 i,j,k 的顺序没有任何限制。
输入格式
第一行包含一个整数 t(1≤t≤104)——测试用例的数量。随后是每个测试用例的描述。
测试用例的第一行包含一个整数 n(3≤n≤2×105)——序列的长度。
测试用例的第二行包含 n 个整数 a1,a2,a3,…,an(1≤ai≤109)——序列 a 的元素。
所有测试用例中 n 的总和不超过 2×105。
输出格式
对于每个测试用例,输出一个整数——序列 a 中的神奇三元组数量。
测试样例
样例说明
在第一个例子中,序列 a 中有 6 个神奇三元组,分别是 (2,3,5),(2,5,3),(3,2,5),(3,5,2),(5,2,3),(5,3,2)。
在第二个例子中,序列 a 中有一个神奇三元组,为 (2,1,3)。