Bunget Mihai (mihaibun) Dorel este pasionat de feng shui. Astfel, pentru a-şi crea un cadru adecvat meditaţiei, s-a hotărât să scrie pe pereţii casei numere care au un număr prim de divizori. El a găsit n numere, însă nu ştie să le aleagă pe cele potrivite.
Cerința
Se dau n numere naturale. Aflaţi câte dintre acestea au un număr prim de divizori.
Date de intrare
Fișierul de intrare prim013.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale nenule separate prin spații.
Date de ieșire
Fișierul de ieșire prim013.out va conține pe prima linie numărul de numere care au un număr prim de divizori.
Restricții și precizări
1 ≤ n ≤ 1.000.000- numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât
10.000.000
Exemplu:
prim013.in
5 1 3 6 9 625
prim013.out
3
Explicație
Numerele 3,9,625 au 2,3 respectiv 5 divizori, numărul divizorilor fiind prim. În total sunt 3 numere cu numărul divizorilor prim.