Two positive integers are said to be coprime if $1$ is their only common divisor. Given a sequence of positive integers $a_{1}, a_{2}, \ldots, a_{n}$, find the number of pairs of its terms which are coprime.
Input Format
The first line of input contains one integer $n$ ($1 ≤ n ≤ 1\,000\,000$) denoting the length of the sequence. The second line contains n integers $a_{i}$ ($1 ≤ a_{i} ≤ 3\,000\,000$).
Output Format
Your program should output one integer representing the number of pairs $(i, j)$ such that $1 ≤ i < j ≤ n$ and $a_{i}$ is coprime with $a_{j}$.
Example
Input
5 3 6 4 7 3
Output
6