distrugere

Considerăm un șir format din $N$ numere naturale. Definim operația distrugere-X astfel:

• se alege un număr natural $X$ care apare în șir;
• se șterg toate numerele din șir care au cel puțin un divizor comun cu $X$ mai mare decât $1$.

Operația distrugere-X se aplică o singură dată.

Cerință

Scrieți un program care, cunoscând $N$ și elementele șirului, determină numărul maxim de elemente care pot să rămână în șir după aplicarea unei singure operații distrugere-X.

Date de intrare

Fișierul de intrare distrugere.in conține pe prima linie numărul natural $N$, cu semnificația din enunț. Pe cea de-a doua linie se află $N$ numere naturale separate prin câte un spațiu, reprezentând elementele șirului.

Date de ieșire

Fișierul de ieșire distrugere.out conține o singură linie pe care este scris numărul maxim de elemente care pot rămâne în șir după aplicarea unei singure operații distrugere-X.

Restricții și precizări

• $2 \leq N \leq 200 \ 000$;
• $1 \leq$ elementele șirului $\leq 1 \ 000 \ 000$.

Exemplu

distrugere.in

4
15 2 6 9

distrugere.out

2

Explicație

Există $4$ variante de alegere a valorii $X$:

• $X = 15$: se elimină $6$, $9$, $15$ și rămâne $1$ element ($2$).
• $X = 2$: se elimină $2$, $6$ și rămân $2$ elemente ($9$, $15$);
• $X = 6$: se elimină $2$, $6$, $9$, $15$ și rămân $0$ elemente;
• $X = 9$: se elimină $6$, $9$, $15$ și rămâne $1$ element ($2$);

Numărul maxim de elemente rămase este $2$.