Yunho the Potion Thief

Hyobin's magic factory sells potions carrying product numbers from 2 to $N$. Yunho bought $M$ of them and decided to open a potion shop. Yeongseon, Yunho's informant, told him Hyobin's secret. If a product $A$ was made by mixing potions with product numbers $P_1, P_2, \dots, P_k$, then the product number of $A$ is $P_1 \times P_2 \times \cdots \times P_k$, and there is no exception. Those $P_1, P_2, \dots, P_k$ are the ingredients of $A$. Hyobin noticed all this and cut Yunho off. What Yunho still has is the $M$ potions he bought and the magic machine his father left him.

The machine decomposes a potion $A$ and pulls out one potion that can be an ingredient of $A$, that is, one potion whose product number divides the product number of $A$ and is at least 2. The decomposed potion $A$ is destroyed. For example, decomposing potion 12 yields one of potions 2, 3, 4, 6 and 12. Yunho wants potions whose effects do not overlap, so the extracted potions must not share an ingredient. Suppose Yunho decomposes $q$ potions and pulls out potions with product numbers $Y_1, Y_2, \dots, Y_q$. If some potion $K$ can be an ingredient of $Y_i$ and can also be an ingredient of $Y_j$ for $i \neq j$, the extraction fails. For example, say Yunho bought potions 12 and 18. Decomposing 12 into potion 4 and 18 into potion 6 fails, because potion 2 can be an ingredient of both. Pulling out 4 and 9 succeeds, because no potion number can be an ingredient of both. Find the largest number of potions Yunho can pull out without failing.

The first line contains $N$ and $M$. ($2 \le N \le 100\,000\,000$, $1 \le M \le 1\,000$)

The second line contains $M$ integers, the product numbers of the potions Yunho bought from Hyobin. Each number is at least 2 and at most $N$.

Print on one line the largest number of potions Yunho can pull out without failing.