== include(page="template/taskheader" task_id="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.
Unul dintre stramosii lui Marcel, Manchaary, fiul lui Nyurgun si Sahayaana, a fost unul dintre servitorii lui Tygyn Darkhan, la inceputul secolului al 17-lea. Tygyn Darkhan, liderul maret care a unificat triburile Yakutiene, parea sa fi fost foarte pasionat despre Teoria Numerelor.
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:
Intr-o zi, a atribuit un numar natural distinct de la $2$ la $M$ celor $N$ vaci ale sale. S-a gandit sa grupeze vacile, bazandu-se pe numerele de pe ele, intr-un numar minim de turme. Totusi, a stabilit urmatoarele conditii, care trebuie satisfacute pentru toate turmele:
* 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.
* Fie $x$ cel mai mic numar atribuit vacilor dintr-o turma. Fiecare vaca din aceeasi turma trebuie sa aiba un numar de forma $x * k$, unde $k$ este un numar natural.
* Toti divizorii primi ai lui $k$ (in afara de 1) trebuie sa fie mai mari sau egali cu orice divizor prim al lui $x$ pentru toate vacile din turma.
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!
Totusi, Tygyn este putin ocupat cu mentinerea pacii pe teritoriul sau, asa ca l-a rugat pe Manchaary sa aiba grija de vaci. Aceasta sarcina parea destul de dificila pentru Manchaary, dar recompensa era minunata: putea sa se casatoreasca cu frumoasa 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!
Stim finalul povestii: Manchaary a rezolvat sarcina si Sardaana a devenit unul dintre stramosii lui Marcel. Totusi, atunci cand Marcel a aflat despre poveste, s-a gandit ca problema poate sa se intoarca la taramurile de provenienta. De aceea, participantii de la Tuymaada 2019 trebuie sa o rezolve!
h2. Input
h2. Date de intrare
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.
Fisierul de intrare $tygyn.in$ contine pe prima linie numerele naturale $N$ si $M$. Urmatoarea linie contine $N$ numere cu valori intre $2$ si $M$, reprezentand numerele distincte atribuite celor $N$ vaci ale lui Tygyn Darkhan.
h2. Output
h2. Date de iesire
Output file $tygyn.out$ contains the minimal number of herds Manchaary could group the cows into.
Fisierul de iesire $tygyn.out$ contine numarul minim de turme in care Manchaary poate grupa vacile.
h2. Constraints
h2. Restrictii si precizari
* $1 ≤ N < M ≤ 1.000.000$
* For $40$ points, $N ≤ 1.000$
* Pentru $10$ puncte, $M ≤ 20$
* Pentru $40$ de puncte, $N ≤ 1.000$
* Evaluarea este diferita fata de cea din timpul concursului oficial.
h2. Example
h2. Exemplu
table(example). |_. tygyn.in |_. tygyn.out |
| 5 100
2 3 11 22 12
| 3
|
| 3 |
| 10 20
8 12 20 6 3 7 11 13 19 15
| 9
