Given an array a of N numbers , you have to find the number of pair of indices *i* and *j* that satisfy the following relation:

- i < j
- a
_{i}> a_{j} - gcd( a
_{i}, a_{j})=1

**Input**

The first line of the input contains a single integer N - denoting the size of the array.

The next line contains N space separated integers denoting the array a.

**Output**

Output a single integer - the answer to the problem stated above.

**Constraints**

1<=N<=10^{5}

1<=a_{i}<=10^{5}