# Magic Triples (Easy Version) solution codeforces

Magic Triples (Easy Version)

time limit per test

4 seconds

memory limit per test

256 megabytes

This is the easy version of the problem. The only difference is that in this version, ai106ai≤106.

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

• 1i,j,kn1≤i,j,k≤n.
• iijjkk are pairwise distinct.
• there exists a positive integer bb such that aib=ajai⋅b=aj and ajb=akaj⋅b=ak.

Kolya received a sequence of integers aa 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 iijj and kk.

Input

The first line contains a single integer tt (1t1041≤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 nn (3n21053≤n≤2⋅105) — the length of the sequence.

The second line of the test contains nn integers a1,a2,a3,,ana1,a2,a3,…,an (1ai1061≤ai≤106) — the elements of the sequence aa.

The sum of nn over all test cases does not exceed 21052⋅105.

Output

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

Example

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

Note

In the first example, there are 66 magic triples for the sequence aa — (2,3,5)(2,3,5)(2,5,3)(2,5,3)(3,2,5)(3,2,5)(3,5,2)(3,5,2)(5,2,3)(5,2,3)(5,3,2)(5,3,2).

In the second example, there is a single magic triple for the sequence aa — (2,1,3)(2,1,3).