Irreducible Fractions

Time limit3sMemory limit2048 MB

Summary

Count ordered index quadruples (i, j, k, l) of distinct positions so that (a_i * a_j) / (a_k * a_l) is an irreducible fraction, with n up to 2000 and values up to 1e12.

Level: Medium6 of 10
Topics: Number theory, Bit manipulation, Combinatorics
Solved: No attempts yet

Problem

Given an array $a$ of $n$ positive integers, count the quadruples of distinct indices $(i, j, k, l)$ for which the following fraction is irreducible:

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

Input

The first line contains an integer $n$ ( $4 \leq n \leq 2000$ ), 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

Print a single integer: the number of quadruples that satisfy the condition.

Examples2

Example 1
Input
```
4
1 1 1 1
```
Expected output
```
24
```
Example 2
Input
```
6
10 11 2 4 5 7
```
Expected output
```
96
```