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