Coprime Numbers

Two positive integers are called coprime if their only common divisor is $1$. Given a sequence of positive integers $a_1, a_2, \dots, a_n$, count how many pairs of its terms are coprime.

The first line contains one integer $n$ ($1 \le n \le 10^6$), the length of the sequence. The second line contains $n$ integers $a_i$ ($1 \le a_i \le 3 \times 10^6$), separated by spaces.

Print a single integer: the number of pairs $(i, j)$ with $1 \le i < j \le n$ such that $a_i$ and $a_j$ are coprime.