#P1627D. Not Adding

    ID: 1447 Type: RemoteJudge 2000ms 256MiB Tried: 0 Accepted: 0 Difficulty: 6 Uploaded By: Tags>brute forcedpmathnumber theory*1900

Not Adding

Description

You have an array a1,a2,,ana_1, a_2, \dots, a_n consisting of nn distinct integers. You are allowed to perform the following operation on it:

  • Choose two elements from the array aia_i and aja_j (iji \ne j) such that gcd(ai,aj)\gcd(a_i, a_j) is not present in the array, and add gcd(ai,aj)\gcd(a_i, a_j) to the end of the array. Here gcd(x,y)\gcd(x, y) denotes greatest common divisor (GCD) of integers xx and yy.

Note that the array changes after each operation, and the subsequent operations are performed on the new array.

What is the maximum number of times you can perform the operation on the array?

The first line consists of a single integer nn (2n1062 \le n \le 10^6).

The second line consists of nn integers a1,a2,,ana_1, a_2, \dots, a_n (1ai1061 \leq a_i \leq 10^6). All aia_i are distinct.

Output a single line containing one integer — the maximum number of times the operation can be performed on the given array.

Input

The first line consists of a single integer nn (2n1062 \le n \le 10^6).

The second line consists of nn integers a1,a2,,ana_1, a_2, \dots, a_n (1ai1061 \leq a_i \leq 10^6). All aia_i are distinct.

Output

Output a single line containing one integer — the maximum number of times the operation can be performed on the given array.

Sample Input 1

5
4 20 1 25 30

Sample Output 1

3

Sample Input 2

3
6 10 15

Sample Output 2

4

Note

In the first example, one of the ways to perform maximum number of operations on the array is:

  • Pick i=1,j=5i = 1, j= 5 and add gcd(a1,a5)=gcd(4,30)=2\gcd(a_1, a_5) = \gcd(4, 30) = 2 to the array.
  • Pick i=2,j=4i = 2, j= 4 and add gcd(a2,a4)=gcd(20,25)=5\gcd(a_2, a_4) = \gcd(20, 25) = 5 to the array.
  • Pick i=2,j=5i = 2, j= 5 and add gcd(a2,a5)=gcd(20,30)=10\gcd(a_2, a_5) = \gcd(20, 30) = 10 to the array.

It can be proved that there is no way to perform more than 33 operations on the original array.

In the second example one can add 33, then 11, then 55, and 22.