Coprime Numbers

Memory limit: 128 MB

Two positive integers are said to be coprime if 1 is their only common divisor. Given a sequence of positive integers , find the number of pairs of its terms which are coprime.

Input

The first line of input contains one integer () denoting the length of the sequence. The second line contains integers ().

Output

Your program should output one integer representing the number of pairs such that and is coprime with .

Example

For the input data:

5
3 6 4 7 3

the correct result is:

6

Task author: Jakub Lacki.