Irreducible Fractions

Given an array $a$ consisting of $n$ positive integers, find the number of quadruples of distinct indices $(i, j, k, l)$ such that the following fraction is irreducible:

$$\frac{a_i \cdot a_j}{a_k \cdot a_l}\text{.}$$

The first line contains an integer $n$ ($4 \leq n \leq 2000$) denoting the length of the array. The second line contains $n$ integers $a_i$ ($1 \leq a_i \leq 10^{12}$), the elements of the array.

Output a single integer: the number of quadruples satisfying the given condition.