윤호는 마법약 도둑

효빈이의 마법 공장은 2번부터 $N$번까지 제품 번호가 붙은 마법약을 판다. 윤호는 그중 $M$개를 사서 마법 상점을 열기로 했다. 윤호의 정보원 영선이가 알려준 효빈이의 비밀은 이렇다. 어떤 제품 $A$를 제품 번호가 $P_1, P_2, \dots, P_k$인 마법약을 섞어 만들었다면 $A$의 제품 번호는 $P_1 \times P_2 \times \cdots \times P_k$가 되고, 예외는 없다. 이때 $P_1, P_2, \dots, P_k$는 $A$의 재료다. 그런데 똑똑한 효빈이가 이를 눈치채고 윤호와의 거래를 끊어 버렸다. 윤호에게 남은 것은 사 온 마법약 $M$개와 아버지께서 물려주신 마법 기계뿐이다.

마법 기계는 마법약 $A$를 분해해서 $A$의 재료가 될 수 있는 마법약 하나를 뽑아낸다. 즉 제품 번호가 $A$의 제품 번호를 나누고 2 이상인 마법약 하나를 얻는다. 분해한 마법약 $A$는 파괴된다. 예를 들어 12번 마법약을 분해하면 2번, 3번, 4번, 6번, 12번 중 하나를 뽑아낼 수 있다. 윤호는 효능이 겹치지 않는 마법약을 모으고 싶어서, 뽑아낸 마법약끼리 재료를 공유하지 않기를 원한다. 윤호가 마법약 $q$개를 분해해 제품 번호가 $Y_1, Y_2, \dots, Y_q$인 마법약을 뽑았다고 하자. $i \neq j$인 어떤 $K$번 마법약이 $Y_i$의 재료도 될 수 있고 $Y_j$의 재료도 될 수 있다면 그 추출은 실패다. 예를 들어 윤호가 사 온 약이 12번과 18번일 때, 12번을 분해해 4번을 뽑고 18번을 분해해 6번을 뽑으면 2번이 두 약 모두의 재료가 될 수 있으므로 실패한 추출이다. 반면 4번과 9번을 뽑으면 어떤 번호도 두 약의 재료가 될 수 없으므로 성공한 추출이다. 윤호가 실패하지 않으면서 뽑을 수 있는 마법약의 최대 개수를 구하라.

첫 줄에 $N$과 $M$이 주어진다. ($2 \le N \le 100\,000\,000$, $1 \le M \le 1\,000$)

둘째 줄에 정수 $M$개가 주어진다. 이 수는 윤호가 효빈이에게 사 온 마법약의 제품 번호다. 각 번호는 2 이상 $N$ 이하다.

윤호가 실패하지 않으면서 뽑을 수 있는 마법약의 최대 개수를 한 줄에 출력한다.