Magic Triples (Hard Version)

time limit per test4 seconds

memory limit per test256 megabytes

inputstandard input

outputstandard output

This is the hard version of the problem. The only difference is that in this version, ai≤109.

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 ai⋅b=aj and aj⋅b=ak.

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≤t≤104) — 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⋅105) — the length of the sequence.

The second line of the test contains n integers a1,a2,a3,…,an (1≤ai≤109) — the elements of the sequence a.

The sum of n over all test cases does not exceed 2⋅105.

Output

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

Example

inputCopy

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

outputCopy

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).