chocolate

We have a list x1,...,xN of pairwise different positive numbers. In one step we choose a number a from the list. We delete a and exchange for a chocolate if there is a b in the remaining list that divides a. This step can be repeated as long as we find appropriate numbers in the remaining list. What is the maximal amount of chocolate that we can get this way?

Example

  N=9
  the list: 12,5,7,8,9,3,11,2,4
  12  : chocolate (divisible by 2)
   5  : -
   7  : -
   8  : chocolate (divisible by 2)
   9  : chocolate (divisible by 3)
   1  : -
   3  : -
  11  : -
   2  : -
   4  : chocolate (divisible by 2)

Input Specification

N
x1 ... xN

The first line is the number 1 ≤ N ≤ 105. The second row is the members of the list separated by space. The numbers in the list are pairwise different integers between 2 and 106

Output Specification

M

A single line with the number M.

Sample Input 1

1. 9
2. 12 5 7 8 9 3 11 2 4

download as text file

Sample Output 1

1. 4

download as text file

Sample Input 2

1. 9
2. 124 58 23 38 6 7 11 13 17

download as text file

Sample Output 2

1. 0

download as text file