시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 2048 MB32266.667%

문제

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.

예제 입력 1

4
1 1 1 1

예제 출력 1

24

예제 입력 2

6
10 11 2 4 5 7

예제 출력 2

96