write a go solution for Description:
This is the hard version of the problem. The only difference is that in this version, a_i<=10^9.

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

- 1<=i,j,k<=n.
- i, j, k are pairwise distinct.
- there exists a positive integer b such that a_i*b=a_j and a_j*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 Format:
The first line contains a single integer t (1<=t<=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<=n<=2*10^5) — the length of the sequence.

The second line of the test contains n integers a_1,a_2,a_3,...,a_n (1<=a_i<=10^9) — the elements of the sequence a.

The sum of n over all test cases does not exceed 2*10^5.

Output Format:
For each test case, output a single integer — the number of magic triples for the sequence a.

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).. Output only the code with no comments, explanation, or additional text.