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