Product Triplets

★★★★★

1 votes

Hard

Details

Problem

Given N integers A₁, A₂, ..., A_N, count the number of triplets (x, y, z) (with 1 ≤ x < y < z ≤ N) such that at least one of the following is true:

A_x = A_y × A_z, and/or
A_y = A_x × A_z, and/or
A_z = A_x × A_y

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each begins with one line containing an integer N: the number of integers in array A. The second line consists of N integers A_i; the i-th of these is the value of the i-th integer, as described above.

Output

For each test case, output one line containing the number of triplets satisfying the condition given in the problem statement.

Limits

1 ≤ T ≤ 30.
0 ≤ A_i ≤ 2 × 10⁵, for all i.

Small dataset

3 ≤ N ≤ 200.

Large dataset

3 ≤ N ≤ 7000.

Sample Input

4
6
5 2 4 6 3 1
6
2 4 8 16 32 64
3
1 1 1
3
200000 200000 200000

Sample Output

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

In Sample Case #1, the only triplet satisfying the condition given in the problem statement is (2, 4, 5). The triplet is valid since the second, fourth, and fifth integers are 2, 6, and 3, and 2 × 3 = 6.

In Sample Case #2, the six triplets satisfying the condition given in the problem statement are: (1, 2, 3), (1, 3, 4), (1, 4, 5), (1, 5, 6), (2, 3, 5), (2, 4, 6).

In Sample Case #3, make sure you only count the triplet (1, 2, 3) once.

In Sample Case #4, there is no triplet satisfying the condition given in the problem statement since the product of any pair of integers in the array will not be in the array.

Contributers:

PEC-ACM