Problem G
GCD Pairs
In the Shape Galaxy, where all shapes are sentient beings, there is currently a feud between circles and squares. Circles want all pathways to be flat while squares argue that they should be evenly spaced inverted catenary shaped bumps. Because of this feud, circles have begun to dislike all square-biased numbers. A number $s$ is square-biased if it is divisible by $x^2$, for some integer $x > 1$.
Mr. Circle has taken this feud to heart. He is given the assignment of calculating the greatest common divisor between all pairs of numbers in an array. He wants to go one step further and count the number of greatest common divisors that are not square biased.
Input
The first line of input contains a single integer, $n$ $(1 \le n \le 10^5)$, representing the length of the array of numbers.
The next $n$ lines contain the integers $a_i$ $(1 \le a_i \le 10^{12})$ which comprise the numbers in the array.
Output
Output a single integer, the number of pairs $(i, j)$ $(1 \le i < j \le n)$ such that $\gcd (a_i, a_j)$ is not square-biased.
| Sample Input 1 | Sample Output 1 |
|---|---|
6 3 4 6 12 4 1 |
12 |
