Fişierul intrare/ieşire:	tygyn.in, tygyn.out	Sursă	Tuymaada 2019
Autor	Alexandru Petrescu	Adăugată de	Alexandru Petrescu •alexpetrescu
Timp execuţie pe test	0.35 sec	Limită de memorie	262144 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Tygyn

One of Marcel's ancestors, called Manchaary, son of Nyurgun and Sahayaana, was one of the servants of Tygyn Darkhan, at the beginning of the 17th century. Tygyn Darkhan, the great leader who unified the Yakutian tribes, seems to have been very passionate about Number Theory.

One day, he assigned some distinct integers from 2 to M to his N cows. He decided to group the cows, based on their numbers, into as few herds as possible. However, he set the following conditions that should be met for all herds:

• Let x be the smallest number assigned to the cows in the herd. Each other number of a cow in the herd is of the form x * k, with k integer.
• All divisors of k (apart from 1) are greater than or equal to any prime divisor of x, for all cows in the herd.

However, Tygyn is a bit busy with keeping peace in his territory, so he asked Manchaary to take care of the cows. The task was rather difficult for Manchaary, but the reward was magnificent: he could then marry beautiful Sardaana!

We know the end of the story: Manchaary solved the task and Sardaana became an ancestor of Marcel. However, when Marcel learned about the story, he thought the task can go back to the lands it originated. That is why the participants in Tuymaada 2019 have to solve it!

Input

Input file tygyn.in contains on the first line the integer numbers N and M. The next line contains N numbers with values between 2 and M, representing the distinct numbers assigned to the N cows of Tygyn Darkhan.

Output

Output file tygyn.out contains the minimal number of herds Manchaary could group the cows into.

Constraints

• 1 ≤ N < M ≤ 1.000.000
• For 40 points, N ≤ 1.000
• Note that the scoring is not the same as the one in the official onsite contest

Example

Tutorial

You can see a O(N + M) solution description in problem's editorial

Request

Contacteaza-l pe autor daca te oferi sa traduci enuntul in limba romana.

Cum se trimit solutii?