**Time limit:**1.00 s**Memory limit:**512 MB

Given a list of n positive integers, your task is to count the number of pairs of integers that are coprime (i.e., their greatest common divisor is one).

# Input

The first input line has an integer n: the number of elements.

The next line has n integers x_1,x_2,\dots,x_n: the contents of the list.

# Output

Print one integer: the answer for the task.

# Constraints

- 1 \le n \le 10^5
- 1 \le x_i \le 10^6

# Example

Input:

8 5 4 20 1 16 17 5 15

Output:

19